CSCI2100/ESTR2102 Data Structures | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Offered by Yufei TAO, Fall 2018. Tutors: Shangqi LU (sqlu@cse) and Jianwen ZHAO (jwzhao@cse). Quick navigation links: [Lecture Notes][Tutorials][Regular Exercises][Special Exercises][Notes for ESTR2102][Quizzes and Exams][Project] |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Brief Description | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
In this course, we will study the fundamental data structures and algorithms. Such knowledge is at the core of computer science, and allows us to write faster programs, especially ones whose running time has attractive worst-case bounds. Techniques for analyzing the performance of algorithms will also be discussed in detail. Tentative topics to be covered include searching in ordered lists, hashing, sorting, priority queues, binary search trees, fundamental graph algorithms, and so on. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Announcements | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
News 15 (3 Dec): Stats of Quiz 3 released. News 14 (28 Nov): Scope of the Final Exam: (i) for CSCI2100, Lec Notes 1-22; (ii) for ESTR2102, Lec Notes 1-22 plus Elite Lec Notes 1-6, 8-9, 11-12. News 13 (14 Nov): Quiz 3 will take place in the lecture of 27 Nov. It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lecture Notes 14-17. You are free to bring in the notes and textbook. New 12 (13 Nov): Project released. See the bottom of the page. New 11 (8 Nov): Stats of Quiz 2 released. News 10 (1 Nov): The final exam will be from 12:30pm to 2:30pm, on 19 Dec. For the venue, pay attention to the university's announcements. News 9 (13 Oct): Quiz 2 will take place in the lecture of 30 Oct. It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lecture Notes 6-13 (Notes 11-13 will be taught in the next two weeks). You are free to bring in the notes and textbook. News 8 (13 Oct): Midterm will take place in the lecture of 22 Oct. It will start at 9:30am and will be 45 minutes long. The scope covers everything in Lecture Notes 1-10. You are free to bring in the notes and textbook. For CSCI2100: 35% of the questions will come from Special Ex Lists 1-5. News 7 (10 Oct): Stats of Quiz 1 released -- see the bottom of the page. News 6 (9 Oct): Regular and special exercise lists 4 and 5 released. There will be no more annoucements about exercise releases. Check the webpage after the lectures each week for this purpose. News 5 (24 Sep): Quiz 1 will take place in the lecture of 2 Oct. It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lecture Notes 1-5. You are free to bring in the notes and textbook. News 4 (24 Sep): Regular and special exercise list 3 released. News 3 (12 Sep): Released regular exercise lists 1 and 2, and special exercise lists 1 and 2. News 2 (3 Sep): There will be no tutorials in the first week. News 1 (2 Sep): Hello, all. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Time and Venues | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Lectures
Tutorials
Click here for a map of the campus. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Grading Scheme | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
In-Class Quiz 1: 5% In-Class Quiz 2: 5% In-Class Quiz 3: 5% Midterm Exam: 20% Coding project: 15% Final Exam: 50% Style of Exams for CSCI2100: During this course, the instructor will gradually generate a list of special exercises without the solutions given. In the midterm and final exams, 35% of the marks will come from problems taken directly from that list. The rest 65%, however, will be from new problems. In the final exam, you will be allowed to bring in a single-sided, A4-sized, note-sheet on which you can print/write anything you deem useful. The midterm will be open book. Style of Exams for ESTR2102: All problems may be new. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Lecture Notes and Textbook | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The instructor recommends the following textbook: Introduction to Algorithms, 3rd Edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Ownership of the book is not compulsory. The instructor will make lecture notes available before each lecture. His notes will be self-contained, namely, containing all the details required in this course. Lecture attendance is vital to grasp the material taught.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Tutorial Material | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Notes for ESTR2102 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Students of CSCI2100 are not required to understand the following material.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Regular Exercises | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The instructor has prepared the following exercises which he believes are useful for students to consolidate their understanding of the course material. Unlike the "special" exercises (see the next section), solutions to these "regular" exercises are provided in full. Exercises carrying one or more stars ("*") may be difficult. The more stars, the more difficult. List 1 (Solutions). List 2 (Solutions). List 3 (Solutions). List 4 (Solutions). List 5 (Solutions). List 6 (Solutions). List 7 (Solutions). List 8 (Solutions). List 9 (Solutions). List 10 (Solutions). List 11 (Solutions). List 12 (Solutions). List 13 (Solutions). There will be no more regular exercises. Additional Exercises If a Textbook Is Owned [Growth of Functions] Exercises 2.2-1, 3.1-2, 3.1-3, 3.1-4, 3.2-4, 3.2-8. [k-Selection] Exercises 9.3-6, 9.3-9, Problem 9-2. [Sorting] Exercises 8.1-3*, 8.1-4*, 8.2-4, 8-5*. [Linked List] Exercises 10.2-6. [Hashing] Exercises 11.2-5, 11.3-5*, Problem 11-2. [Priority Queue] Exercises 6.1-4, 6.5-9, Problem 6-3. [AVL-Tree] Exercises 12.1-3, 12.1-5, 12.2-5, 12.2-6, Problems 12-2, 13-1. [Graph Basics] Exercises 22.1-5, 22.1-6*. [BFS] Exercises 22.2-5, 22.2-7, 22.2-8. [DFS] Exercises 22.3-4, 22.3-7, 22.3-8, 22.3-10. [Topological Sort] Exercises 22.4-2, 22.4-3, 22.4-5. [Fundamental Graph Challenges] Problems 22-2(e-h), 22-3, 22-4. [SSSP] Exercises 24.3-6*, 24.3-7. [MST] Exercises 23.1-3, 23.1-5, 23.1-8, 23.1-9, 23.1-10, 23.1-11. Problems 23-1, 23-4*. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Special Exercises | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
As mentioned earlier, some problems in the midterm and final exams of CSCI2100 will be taken directly from the special exercise lists below. No solutions to these exercises will be given. You are free to look for the solutions in any way (e.g., you may discuss them with your friends, the tutors, or even the instructor himself). Remember: during the exams, you will be allowed to consult only one piece of single-sided A4-sized paper. In other words, it is unrealisic to hope that you can write down all the solutions on that paper. You will need to comprehend the solutions to make sure you can answer them correctly in the exams. Special exercises in general are easier than regular exercises. List 1. List 2. List 3. List 4. List 5. List 6. List 7. List 8. List 9. List 10. List 11. List 12. List 13. There will be no more special exercises. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Quizzes and Exams | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Quiz 1 Stats: CSCI2100: max = 100, average = 72.1, standard deviation = 22.5. Top 20 scores (class size = 78) ESTR2102: max = 100, average = 92, standard deviation = 4.1 (class size = 7). Midterm Stats: CSCI2100: max = 100, average = 60.9, standard deviation = 23.2. Top 20 scores ESTR2102 (different paper): max = 99, average = 66.7, standard Deviation = 24.2. Quiz 2 Stats: CSCI2100: max = 100, average = 74.9, standard deviation = 22.2. Top 20 scores ESTR2102: max = 100, average = 73.9, standard deviation = 24.2. Quiz 3 Stats: CSCI2100: max = 100, average = 70.6, standard deviation = 26.7. Top 20 scores ESTR2102: max = 100, average = 79.7, standard deviation = 27.6. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Project | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Description (released at 7pm, 13 Nov). Deadline: 11:59pm, 16 Dec, 2018. Click here to download half of the operation dataset (the other half is hidden from you, as explained in the description). Note: Use a "good" text editor to open the file. Do not use the NotePad that comes with Windows. An assessment item has been created in the Blackboard system. Please follow the instructions there to submit your project. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|