Comprehensive Final Exam Preparation for Computer Science Students
The final exam will be held on Saturday, April 20, from 8:30 to 11:00 am in room B9201. It will be similar in style to the midterm exam but longer and more comprehensive, covering topics such as abstract data types, data structures, object-oriented design principles, time efficiency analysis, recursive thinking, tree definitions and traversals, balanced trees, and hash tables. The exam will be closed-book and may include a coding component on paper. Be prepared by reviewing lecture slides and sample finals sent via email.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Saturday, April 20, 8:30-11:00am in B9201 Similar in style to written midterm exam May include (a little) coding on paper About 1.5 times as long as midterm See sample final via email Final exam is cumulative More weight on latter half Closed-book, etc.
Exam will cover almost all material in assignments and labs Except templates, operator overloads Exam will cover almost all material in lecture slides Details of exceptions to follow
Abstract Data Types Data Structures Stacks Queues Array and Linked List implementations Dynamic (heap) versus Static (stack) memory
Object-oriented design principles Basics of classes Pointers Memory management Dangling pointers Memory leaks
Methods for analyzing time efficiency O-notation And others Best, worst, average case Sorting Insertion sort Selection sort Quicksort
Thinking recursively Formulating recursive solutions to problems Writing recursive functions Efficiency of recursive functions MergeSort
Definitions Trees, perfect trees, complete trees Tree traversals In-order, pre-order, post-order Binary search tree Insertion, deletion, search algorithms
Balanced trees Definition of red-black tree Properties of red-black trees No proofs, but you should have intuitive understanding Tree rotations Red-black tree algorithms Don t need full algorithm in your head, but you should be able to follow the examples in the slides
Hash tables Hash functions Resolving collisions Open addressing Linear probing, quadratic probing, double hashing Separate chaining
ADT priority queue Heap data structure Heap algorithms Insertion, removal BubbleUp and BubbleDown Heap implementation using an array Heapsort
Disk access versus memory access Algorithms focus on minimizing disk accesses NOT: M-way trees, B-trees External sorting Mergesort Why are other algorithms slow?
Thanks for all your hard work this term! Good luck on the exam
