CS 202: Fundamental Structures of Computer Science II

CS 202: Fundamental Structures of Computer Science II
Spring '12

Announcements

May 21	The final exam will be held on Monday, May 21st. It will be a closed-book and closed-notes exam and no A4 sheet will be allowed. Exam locations: BZ01: Section 1 (Arsan - Komurcu) BZ02: Section 1 (Kurnaz - Yildirim), Section 2 (Acar - Aydin) BZ04: Section 2 (Aytac - Orhan) BZ05: Section 2 (Onder - Yuksel)

May 4	Homework 5 has been posted. It is due by 11:59 pm on Wednesday, May 16th.

Apr 16	Homework 4 has been posted. It is due by 11:59 pm on Monday, April 30th.

Apr 12	The second midterm exam will be held on Monday, April 16th. It will be a closed-book and closed-notes exam and no A4 sheet will be allowed. Exam locations: EB 201: Section 1 (Arsan - Komurcu) EB 203: Section 1 (Kurnaz - Yildirim), Section 2 (Acar - Aydin) EB 202: Section 2 (Aytac - Orhan) EB 204: Section 2 (Onder - Yuksel)

Apr 3	Homework 3 has been posted. It is due by 6:00 pm on Monday, April 16th.

Mar 21	The first midterm exam will be held at EE 03 (Section 1 [all students]), EE 317 (Section 2 [Acar - Karaca]), and EE 517 (Section 2 [Karahan - Yuksel]) at 17:40-19:40 on March 23, 2012. It will be a closed-book and closed-notes exam and no A4 sheet will be allowed.

Mar 20	Homework 2 has been posted. It is due by 6:00 pm on Monday, April 2nd.

Feb 29	Homework 1 has been posted. It is due by 6:00 pm on Monday, March 12th.

Feb 6	Please check out the syllabus.

Feb 6	Welcome to CS 202! Please check this web page for announcements.

Course Description

The course discusses concepts related with algorithmic efficiency on basic abstract data types. First, the course introduces algorithmic efficiency on basic abstract data types and some sorting algorithms that utilize recursion. Then the course discusses the abstract data types of trees, tables, priority queues, and graphs. It also shows how one can implement these abstract data types in C++ using fundamental data structures by emphasizing run-time complexity analysis.

Instructors:

Cigdem Gunduz Demir (Section 1)
EA 423 (Engineering Building), x3443
gunduz at cs bilkent edu tr
Office hours: Tue 12:40-14:30

Tolga Capin (Section 2)
EA 207 (Engineering Building), x3404
tcapin at cs bilkent edu tr
Office hours: Mon 15:40-17:30

TAs:

Sami Arpa
EA 407 (Engineering Building)
arpa at cs bilkent edu tr
Office hours: TBA

Erdem Ozdemir
EA 425 (Engineering Building)
erdemo at bilkent edu tr
Office hours: TBA

Lectures:

Mon 8:40-10:30, Wed 10:40-11:30, BZ04 (Section 1)

Mon 10:40-12:30, Thu 9:40-10:30, BZ04 (Section 2)

For some weeks, we may use the following extra class hours. You can learn when they are used by following the class announcements and regularly checking your e-mails.

Wed 11:40-12:30, BZ04 (Section 1)

Thu 8:40-9:30, BZ04 (Section 2)

Texts:

(Required) F. M. Carrano, Data Abstraction and Problem Solving with C++: Walls and Mirrors, 5th edition, Addison-Wesley, 2006. (You can also use the other editions.)

(Recommended) H. M. Deitel and P. J. Deitel, C++ How to Program, 5th edition, Prentice Hall, 2005. (You can also use the other editions.)

(Recommended) M.A. Weiss, Data Structures and Algorithm Analysis in C++, Addison-Wesley, 2006.

Grading policy:

Midterm 1	(25%)
Midterm 2	(25%)
Final	(25%)
Homework	(15%)
Quiz	(10%)

Lectures

TOPICS	CONTENTS
Algorithm Analysis [ Slides ]	- Algorithm efficiency - Algorithm analysis - Substitution, recursive trees
Sorting [ Slides ]	- Sorting
Trees [ Slides ]	- Trees - Binary trees - Binary search trees
Priority queues [ Slides ]	- Tables - Priority queues - Heaps - Heapsort
Balanced search trees [ Slides: Part I \| Part 2 ]	- AVL trees - 2-3 trees - 2-3-4 trees - Red-black trees
Hashing [ Slides ]	- Hashing
Graphs [ Slides ]	- Graphs

Exams

The midterms and final will be closed-book and closed-notes exams.
There will be five in-class quizzes. Quizzes will be given in class with advance notice. The quizzes will be closed-book and closed-notes. There will be NO make-up quiz.

Homework

Homework assignments will be posted on this page 2-3 weeks before their due date. Assignments are expected to be turned by 18:00 on the due date. For the late assignments, you will be given a total of three grace days (whole or partial) for the whole semester. Once these late days have been exhausted, no late assignments will be accepted. As an example, if you submit you first assignment 29 hours late, you will have used two late days and have only one day left. If you then submit your second assignment 5 hours late, you will have used your remaining late day. If you submit your third assignment 1 minute late, this assignment will not be accepted.

You have to do your own homework. CHEATING WILL BE HEAVILY PUNISHED.

Important Notes

After you have submitted your homework, we (instructors or TAs) may, randomly and without prior notice, question you on your answers. If you fail to answer these questions to the satisfaction of the TA/instructor, you may be charged with cheating on your homework. So, make sure you do the homework assignments yourself, and do not turn in anything that you do not understand completely.

If your exam total (two midterms and one final exam) is below an acceptable threshold, you will fail regardless of other scores.

Academic Integrity

Copying or communicating during an exam is considered as cheating. Students caught cheating in an exam will be subject to disciplinary action, as explained in the "Student Disciplinary Rules and Regulation". Cheating on homework assignments is prohibited. Students caught cheating on assignments will also be subject to disciplinary action.