cS117: Introduction to Programming Languages C++

Date of Handout:  March 26, 2001
Instructor:    Catalin Dumitrescu, Ryerson 403 Cubicle 16, 
               cldumitr@cs.uchicago.edu

Office Hours:  Monday 10:30 - 12:00, 
               Wednesday 3:00 - 5:00, 
               Friday 10:30 - 12:00, or anytime by apointment

Teaching Assistants: 
               Ivona Bezakova ivona@cs.uchicago.edu office 163. phone 702.6238 
               Pradyut Shah pradyut+cs117@cs.uchicago.edu office 163. phone 702.6238
               Songyan Feng songyanf@cs.uchicago.edu office 257. MacLab hours Tuesday & Thursday 6:00-9:00

Class web page:  
     http://www.classes.cs.uchicago.edu/classes/archive/2001/fall/CS117/

Textbooks:  

Required:

    Carrano, Helman, Veroff, "Data Abstraction and Problem Solving with C++",
(bookstore)

Optional:

    Mark Allen Weiss, "Data Structures and Algorithm Analysis in C++", 
    ISBN 0-20149-840-5

    Stroustroup, ``The C++ Programming Language, Addison-Wesley''
    ISBN 0-201-88954-4

Course Overview: 

This course covers definition, use, algorithm design and algorithm analysis
of the fundamental abstract data types, including linked lists, stacks, 
queues, trees and graphs. Also, analysis of each algorithm is done. 

Prerequisites:  

One of CS106, CS116 is a prerequisite for this class. Attendance 
at lectures is expected. This course requires a significant C++ programming 
background.

Introduction

1.  Problem Solving. Design Principles p. 3-21
2.  Data Abstraction. p. 105-125
3.  Recursive Solutions. p. 50-80
    Efficiency of Recursion

Lists
4.  List ADT, Array Implementation p. 125-134
5.  List ADT, Pointer-Based Implementation p. 148-170
6.  Circular, Doubly Linked List ADT p. 190-197

7.  Stacks ADT p. 250-272
8.  Applications p. 272-289
9.  Queues ADT. Applications p. 303-324

Sorting
10. Introduction to Sorting p.391-404
    Selection Sort 
11. Bubble Sort p. 407-412
    Insertion Sort
12. Quick Sort p. 417-427
    Merge Sort p. 412-417, 430

13. Comparison of sorting algorithms
    Review
14. Midterm (Wednesday, April 25)
15. Exceptions

Trees
16. Binary Trees. Representations p. 440-455
17. Tree Traversals. General Trees. p. 455-470
18. Binary Search Trees. Insert, Delete, Find p. 470-499

Advanced Implementation of Tables
19. AVL Trees p. 583
20. 2-3 Trees, B-Trees p. 563
21. Priority Queues p. 535 Heaps p. 539
22. Hashing. Methods to avoid collisions p. 598 - 622

23. Disjoint Set ADT

Graphs
24. Graphs. DFS p. 629-637
25. BFS, Topological Sorting p. 639
26. Minimum Spanning Tree  (App. Graphs & Disjoint Set ADT)
    Shortest Path          (App. Graphs & Priority Queues)
27. External Methods 
28. Exam Review

Homework:

weekly homework, a final mini-project 

Exams:

The Midterm will be in class during 5th week
The Final Exam will be June 8.

Final Grade:

40% homework,
20% midterm, 
10% mini-project,
30% final exam

Academic Honestity:
Programs, homework and examinations are to be completed without 
collaboration with any other person. However, you may discuss with your 
colleagues the general nature of the solutions to programs and homework 
problems. Violations of this policy will be reported, and could result 
in expulsion from the university. In addition, the student will receive a 
zero grade on the program, homework or examination. 

No late assignments will be accepted !!!