Class Schedule

Week 1

Monday 26 August

• introduction to data structures
• introduction to course logistics
• C++ refresher
  • Pima Indians Diabetes Data Set

Wednesday 28 August

• Installing gcc – team project
• Lightning Round. Files you will need:
  • route for task 7
  • auto-mpg.data for tasks 10 &  11
  • gerbil data for task 13
  • Beowulf for task 15
• Individual Task 1: Ghost (new due date: Friday 6 Sept)
  • Scrabble Word List file
• Optional Individual Credit. You can finish the lightning round tasks your team did not complete. To get credit, please demo them to me during my office hours. The Tasks teams DID complete are:
  • Sec 1: Team 1: 1, 2, 4, 8, 9, 12; Team 2: 1; Team 3: 1, 5, 9; Team 4: 1, 4, 9; Team 5: 1, 3
  • Sec 2: Team 1: 1, 3, 9, 12; Team 2: 5, 6, 9; Team 3: 6; Team 4: 1, 3, 5, 6, 9; Team 5: 1, 5

Week 2

Monday 2 September

• RAT 1 (Readiness Assessment Test) Open Data Structures Chapter 1
  • The most important part of the chapter is Big-O notation. Professor Toth said you covered linear and binary search, and bubble sort. You should know the big-O runtime of these algorithms. Suppose I have 2 sorted lists that I want to merge together into one big sorted list. What is the big-O runtime of that algorithm? I will not ask any questions about the math formulas related to Big-O.
  • You should know what an interface is and all the material in section 1.2. In addition to definition-type questions, I may ask questions like “Suppose I want to write a program that checks to see that the braces in a C++ program file are balanced (meaning that there are an equal number of ‘{‘ and ‘}’). Which data structure would I use?
  • You don’t need to know anything from 1.3.1, 1.3.2  and 1.3.4
  • You should know the material in 1.4 and 1.5
• Review of C++ Classes and into to Makefiles
• Partner Task 1
  • rectangleMain.cpp
  • sample makefile

Wednesday 4 September

• Partner Task 1
• Homework 2 walkthrough
  • main.cpp
  • pictures of rules

Week 3

Monday 9 September

• Homework 1: debriefing.
• How to approach small programming problems
• Team Worksheet: Cellular Automaton
• Introduction to Pointers and  Dynamic Memory.
  • Blinky Pointer Video
  • Blinky pointers slides
  • Smart pointer slides
• 20 minute lab to finish partner task.

Wednesday 11 September

• Pointers continued
• Smart Pointers
• Linked Lists
  • pointers1.cpp

Week 4

Monday16 September

• RAT 2: Chapter 3: Linked Lists
• makefiles yet again
• Discussion of HW2.
  • one solution: cellular.h  cellular.cpp
• HW3: RPN Calculator using shared pointers and linked lists
  • hw3.cpp
• linked list partner practice continued
  • loopList.cpp  (can you detect cycles in a linked list?)
  • merge.cpp   (can you merge 2 sorted lists into one sorted list?)
  • finish last week’s pointer task.

Wednesday 18 September

Week 5

Monday23 September

• Finish up on linked list tasks (delete, addafter, detect cycle, merge 2 lists)
• Support for lists, stacks, and queues, in the STL (standard template library)
• Challenge:  Find a path between two cities using breadth-first search.
  • romaniaTemplate.cpp
  • Map of Romania
  • how a priority queue works

Wednesday 25 September

• awesome video that has nothing to do with the class
• review of Homework 3 
• discussion of testing and makefiles
• In class task and homework: Makefiles and unit tests

Week 6

Monday 30 September

• short lab to get ready for demo
• demo – roman numeral and gtest
• Introduction to trees
  • binaryTreeTemplate.cpp

Wednesday 2 October

• Binary Search Tree lab (all optional) 60XP
• stoplist.txt

Week 7

Monday 7 October

• RAT – Binary Trees – Chapter 6  – plus material covered in class.
• Optional Midterm Projects
• Optional explorations on binary trees

Wednesday 9 October

Week 8

Monday 14 October

• Fall Break

Wednesday 16 October

• back from Fall Break
• Sorting
• Sorting Homework
  • sort.h
  • sort_unittest.cc
  • makefile

Week 9

Monday 21 October

• code review and discussion
  • tree methods – LDR, sum, delete, etc.
  • romania code
  • sort functions
• quick map-reduce intro
• hash tables (aka dictionaries, maps)

Wednesday 23 October

• more training and mental calisthenics with hash tables

Week 10

Monday 28 October

• yet more training – command line arguments.

Wednesday 30 October

• Intro to graphs
• Homework: Graphs and class scheduling

Week 11

Monday 4 November

• FEMA partner task: Fun with Graphs
• dijkstraTemplate.cpp
• a.txt
• fema.txt
• supplies.txt
• What the map looks like

Wednesday 6 November

Week 12

Monday 11 November

• Processes & threads
• thread synchronization
• semaphores
• semaphore worksheet

Wednesday 12 November

• Threads, monitors, and condition variables
• Can you convert ConditionVariables2.cpp so that all threads get ready before any of them proceed?
• cokeMachine.cpp before we add the monitor code (so you can follow along with the demo). Coke Machine code with monitors added cokeMachine2.cpp
• Can you alter the code in boundedBuffer.zip so that it implements a bounded buffer?
• FINAL PROJECT WRITEUP

Week 13

Monday 18 November

• Greedy algorithms
• walk through of Final Project task 2
  • binary3.cpp
  • Hawaiian corpus
  • Hsample.txt
• Peer evaluation
• Thread lab

Wednesday 20 November

• Q&A for Final Project
• thread demo
• rest of class only for Level 6 or lower
  • writeup
  • friendsCoworkers.cpp
  • balanceCheck.cpp
  • priority.cpp
  • todo.txt
  • todo.cpp
  • romaniaTemplate33.cpp

Week 14

Monday 25 November

• class only for Level 6 or lower
• tasks continued

Wednesday 27 November

• Thanksgiving Break

Week 15

Monday 2 December

• Divide and Conquer
• Dynamic Programming
• 2 ACM challenges:
  •  Game of Sum (90% of those who try solve this Dynamic Programming problem)
  •  Doublets (only 60% solved this– but I find it easier than the problem above) For a larger problem for debugging you can use the Scrabble wordlist file from week 1!

Wednesday 4 December