CS 202: Fundamental Structures of Computer Science II

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

Announcements



Apr 24	Midterm 2 Exam will be held on April 29, between 18:00 - 20:30, in three classrooms: EB-101, EB-102, EB-103. The exam will cover all topics in the course, until the beginning of the separate chaining subtopic of hashing. Exam locations are as follows: EB-101 : Akgun - Yildirim (Section 1) EB-102 : Yildiz - Zararsiz (Section 1) and Aksoy - Ilgun (Section 2) EB-103 : Kadioglu - Yildiz (Section 2)

Apr 16	Homework 3 has been posted. The deadline is 23:59 on May 5 (Monday), 2014.

Mar 24	Midterm 1 Exam will be held on April 1, between 18:00 - 20:30, in three classrooms: EB-101 EB-102 EB-103. More announcements will be sent by email and also posted here.

Mar 14	Homework 2 has been posted. The deadline is 23:59 on April 3 (Thursday), 2014.

Mar 14	Quiz 3 will be on March 24, 2014. It will be on trees.

Feb 28	Quiz 2 will be on March 10, 2014. It will be on sorting.

Feb 28	Homework 1 has been posted. The deadline is 23:59 on March 10, 2014.

Feb 17	Quiz 1 will be on February 4, 2014. It will be on algorithm analysis.

Feb 12	Please check out the syllabus.

Feb 12	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:

Tolga Capin (Section 1)
EA 529 (Engineering Building), x 3404
tcapin at cs bilkent edu tr
Office hours: Mon 12:40-13:30 and by appointment

Çiğdem Gündüz Demir (Section 2)
EA 423 (Engineering Building), x 3443
gunduz at cs bilkent edu tr
Office hours: Mon 12:40-13:30 and by appointment

TAs:

Gökçen Çimen
EA 527 (Engineering Building)
gokcen.cimen at bilkent edu tr
Office hours: TBA

Can Fahrettim Koyuncu
EA 425 (Engineering Building)
koyuncu at cs bilkent edu tr
Office hours: TBA

Lectures:

Mon 9:30-10:20, Wed 10:30-12:20, EB101 (Section 1)

Mon 10:30-11:20, Thu 8:30-10:20, BZ05 (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.

Mon 8:30-9:20, EB101 (Section 1)

Mon 11:30-12:20, BZ05 (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	(12%)
Quiz	(10%)
Presentation	(3%)

Lectures

TOPICS	CONTENTS
Algorithm Analysis [ Slides ]	- Algorithm efficiency - Algorithm analysis - Substitution, recursive trees
Sorting [ Slides ]	- Sorting
Trees [ Slides ]	- Trees - Binary trees - Binary search trees
Balanced search trees [ Slides: Part I \| Part 2 \| Examples ]	- AVL trees - 2-3 trees - 2-3-4 trees - Red-black trees
Priority queues and heaps [ Slides ]	- Tables - Priority queues - Heaps - Heapsort
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.