CS 223: Computer Science II

Summer 2008

Date	Lecture Topic	Reading
Jun 30	Review 221 Final - Go over Syllabus	Old tests
Jul 1	Trees Advanced Trees Comparable example	Chapter 4.1, 4.2
2	Self Balancing Trees	Chapter 4
3	Red/Black Trees	Chapter 12
7	Hashing	Chapter 8
8	Hashing	Chapter 8
9	Graphs	Chapter 9
10	Shortest Path	Chapter 9
14	Graphs	Chapter 9
15	Heaps	Chapter 6
16	Example test	Chapters 4, 5, 6, 9
17	Review	Chapters 4, 5, 6, 9
21	Test 1/50 minutes Go over test	Chapter 4, 5, 6, 9
22	Huffman - Greedy Algorithms	In Book, look up
23	Dynamic programming	Dynamic Programming
28	Robot work	Maze Algorithms
29	Divide and Conquer	Chapter 10.2
30	Divide and Conquer	Chapter 10.2
31	Backtracking	Chapter -10.5
Aug 4	NP and Intractablility, Turing machines	Chapter -Algorithms
5	NP/P/Turing machines	Chapter Algorithms
6	Review	Chapters 8-12-KW, Chapters
7	Final exam	Comprehensive

Lab Assignments
Date	In-Lab	Out of Lab
Jul 1	Lab 1
3	Lab 2
Jul 8	Lab 3
10	Lab 4
15	Lab 5
17	Lab 6
22	Lab 7
24	Lab 8
29	Lab 9
Aug 31	Lab 10
Aug 5	Lab 11

50% of your grade comes from exams. 50% of your grade comes from the laboratory and classwork. To pass the course, you must average at least 50% on the exams. The final will not be given early.

Instructor

Hunter Lloyd
Office: EPS 357
Phone: 994-5959
Email: hunterl - at symbol - cs.montana.edu

Textbooks

Objects, Abstraction, Data Structures and Design Using Java, by Koffman & Wolfgang.
Introduction to Algorithms, Cormen, Leiserson, Rvest, Stein; McGraw Hill

Course Outcomes

At the end of the course, students should be able to

Use the Java Collections available in the library.
Understand and implement different data structures, including:
Hash tables
Balanced binary search trees
Priority queues implemented as heaps
Graphs

Implement and know the efficiency of many of the common algorithms, including

Searching and sorting algorithms
Floyd's, Prim's, Kruskal's, and Dijkstra's algorithms

Understand when to use some of the algorithm design techniques, including:
Greedy algorithms
Divide and conquer algorithms
Dynamic Programming algorithms