Final Exam

Dear fellow students,
In order to review what you have done in the exam room, you can access the exam questions by following this link. You can also access the answer sheet by following this link and this link.
Thank you for signed up in my class.

Week 13: Exam Overview

Exam Preparation:

• Revisit the lecture contents from week 01 to week 12.
• Working on the exam sample questions.
• Prepare pens with several different colors. You might need them to answer the exam questions clearly.
• Prepare the printed version of the prescribed textbook. You are allowed to bring the printed version of the prescribed textbook in the exam room, but not the digital version.

Marking Scheme:

• Correct Answer: Full Mark
• Precision Error: Half Mark
• Wrong Answer: Zero Mark
• Cheating: Unit Failed

Sample Questions

Week 12: Hash Tables

Learning Resources:

• Prescribed Textbook (sub-chapter 3.4)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Linear Probing Demo 

Tutorial Content:

• Exercises section from Prescribed Textbook (page 480-482)

Self Study:

• Creative Problems section from Prescribed Textbook (page 483-484)
• Experiments section from Prescribed Textbook (page 485)

Week 11: Balanced Search Trees

Learning Resources:

• Prescribed Textbook (sub-chapter 3.3)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• 2-3 Search Tree Demo
• Red-Black BST Demo

Tutorial Content:

• Exercises section from Prescribed Textbook (page 449-450)

Self Study:

• Creative Problems section from Prescribed Textbook (page 451-455)
• Experiments section from Prescribed Textbook (page 456)

Week 10: Binary Search Trees

Learning Resources:

• Prescribed Textbook (sub-chapter 3.2)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Binary Search Tree Demo

Tutorial Content:

• Exercises section from Prescribed Textbook (page 416-418)

Self Study:

• Creative Problems section from Prescribed Textbook (page 419-421)
• Experiments section from Prescribed Textbook (page 422-423)

The Value of Education

Dear fellow students,
I just watch an inspiring presentation about education in Afghanistan, and I feel bad if I'm not share this presentation among you. This is a great presentation that might broaden your perspective about how precious an education is.

This is the link to the presentation.

Imagine a country where girls must sneak out to go to school, with deadly consequences if they get caught learning. This was Afghanistan under the Taliban, and traces of that danger remain today. 22-year-old Shabana Basij-Rasikh runs a school for girls in Afghanistan. She celebrates the power of a family's decision to believe in their daughters -- and tells the story of one brave father who stood up to local threats. (Filmed at TEDxWomen)

This is the link to the presenter's biography.

Cheers,
Budi

Assignment 2: Sorting Applications

Assignment Specification:

• Form a group consist of 3 to 5 students
• Read sub-chapter 2.5 Sorting Applications from the Prescribed Textbook (page 336-351)
• Do the Exercises part: 2.5.1, 2.5.2, 2.5.3, 2.5.4, 2.5.5, 2.5.8
• Use this file as a template for this assignment work.
• This assignment worth 30% of the final mark for this unit (equals to KAT)

Assignment Submission:

• Assignment due date: Tuesday, 28th of May 2013 at 3:00 pm
• Please submit your assignment by sending it to my email address: setia[dot]budi[at]itmaranatha[dot]org
• For the email subject, please follow this format:  [ASSIGNMENT 2: <student id 1>, <student id 2>, ...]
• Example for email subject:  [ASSIGNMENT 2: 1273001, 1273002, 1273003]

Late assignment submission will refer to following marking scheme: 

FM = OM – (OM*LD*0.1)

FM: Final Mark; OM: Original Mark; LD: Late Duration(day)

This unit has an honour code: You are allowed to discuss the material and assignment with your fellow classmates but not to get or share the answer. What you turn in has to be your own work. Cheating and plagiarism act will lead to FAILED mark for your final result of this unit.

If you have any question related to the assignment specification, feel free to ask me. You can simply do it by sending me an email :)

Good luck for the assignment and have fun :)

Week 09: Symbol Tables

Learning Resources:

• Prescribed Textbook (sub-chapter 3.1)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)

Tutorial Content:

• Exercises section from Prescribed Textbook (page 389-390)

Self Study:

• Creative Problems section from Prescribed Textbook (page 391-392)
• Experiments section from Prescribed Textbook (page 393-394)

Week 07: Quick Sort

Learning Resources:

• Prescribed Textbook (sub-chapter 2.3)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Partitioning Methods in Quick Sort
• Dancing with Quick Sort

Tutorial Content:

• Exercises section from Prescribed Textbook (page 303-304)

Self Study:

• Creative Problems section from Prescribed Textbook (page 305-306)
• Experiments section from Prescribed Textbook (page 307)

Week 08: Priority Queue

Learning Resources:

• Prescribed Textbook (sub-chapter 2.4)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Binary Heap Demo
• Heap-sort Demo

Tutorial Content:

• Exercises section from Prescribed Textbook (page 329-330)

Self Study:

• Creative Problems section from Prescribed Textbook (page 331-334)
• Experiments section from Prescribed Textbook (page 335)

Week 06: Merge Sort

Learning Resources:

• Prescribed Textbook (sub-chapter 2.2)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Merging Video
• Dancing with Merge Sort

Tutorial Content:

• Exercises section from Prescribed Textbook (page 284)

Self Study:

• Creative Problems section from Prescribed Textbook (page 285-286)
• Experiments section from Prescribed Textbook (page 287)

Week 05: Elementary Sorts

Learning Resources:

• Prescribed Textbook (sub-chapter 2.1)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Selection Sort Video
• Insertion Sort Video
• Knuth Shuffle Video
• Sorting Dances (video):
• Selection Sort Dance
• Insertion Sort Dance
• Shell Sort Dance

Tutorial Content:

• Exercises section from Prescribed Textbook (page 264)

Self Study:

• Creative Problems section from Prescribed Textbook (page 265-266)
• Experiments section from Prescribed Textbook (page 267-269)

Week 04: Analysis of Algorithms

Learning Resources:

• Prescribed Textbook (sub-chapter 1.4)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Binary Search Video
• Big O, Big Omega, and Big Theta Notation

Tutorial Content:

• Exercises section from Prescribed Textbook (page 208-211)

Self Study:

• Creative Problems section from Prescribed Textbook (page 212-213)
• Experiments section from Prescribed Textbook (page 214-215)

Week 03: Bags, Queues, and Stacks

Learning Resources:

• Prescribed Textbook (sub-chapter 1.3)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Robert Sedgewick)
• Lecture Slide (prepared by Boedy)
• Animation: Dijkstra 2 Stack (prepared by Robert Sedgewick)

Tutorial Content:

• Exercises section from Prescribed Textbook (page 161-166)

Self Study:

• Creative Problems section from Prescribed Textbook (page 167-171)

Week 02: Data Abstraction

Learning Resources:

• Prescribed Textbook (sub-chapter 1.2)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Boedy)

Tutorial Content:

• Exercises section from Prescribed Textbook (page 114-116)

Self Study:

• Creative Problems section from Prescribed Textbook (page 117-119)

Week 01: Basic Programming Model

Learning Resources:

• Prescribed Textbook (sub-chapter 1.1)
• Prescribed Textbook companion website
• Lecture Slide (prepared by Boedy)

Tutorial Content:

• Exercises section from Prescribed Textbook (page 54-58)

Self Study:

• Creative Problems section from Prescribed Textbook (page 59-60)
• Experiments section from Prescribed Textbook (page 61-62)

Unit Outline Semester 1, 2013

Algorithms (IS-207)

Semester 1, 2013

Unit Coordinator

Boedy (setia[dot]budi[at]itmaranatha[dot]org; sbudi[at]utas[dot]edu[dot]au; LinkedIn; Twitter)
H08B04, GWM level 8
Maranatha University

Lecturing Staff

Boedy (setia[dot]budi[at]itmaranatha[dot]org)
Consultation time: Friday 08:00am - 09:00am

Prescribed Textbook

Algorithms (4th Edition)
Author: Robert Sedgewick, Kevin Wayne
Publisher: Addison-Wesley Professional (2011)
ISBN: 978-0-321-57351-3

Unit Plan

• Week 01: Basic Programming Model  
• Week 02: Data Abstraction
• Week 03: Bags, Queues, and Stacks
• Week 04: Analysis of Algorithms 
• Week 05: Elementary Sorts
• Week 06: Mergesort  
• Week 07: Quicksort 
• Week 08: Priority Queues
• Week 09: Symbol Tables
• Week 10: Binary Search Trees
• Week 11: Balanced Search Trees
• Week 12: Hash Tables

Supporting Learning Resources

• Textbook companion website
• On-line Course (delivered by Robert Sedgewick and Kevin Wayne from Princeton University)

Prior Knowledge and/or Skills

Students will be expected to have the following (from prerequisite units and / or their own reading):

• Good English (passive). This skill is essential since there will be reading task (refer to the prescribed textbook) in each week as part of self study.
• An understanding of and ability to use basic programming constructs (variable including arrays, assignment operations, arithmetic operations, logical tests, branching flow of control, looping flow of control) in order to run and implement some algorithms.
• Familiar with Java programming language. This skill is essential since all the code examples in this unit are written in Java.

Programming Tools

• Java (jdk)
• Sublime Text 2
• Standard Libraries
• Standard Libraries as External Libraries (Optional for IDE use)
• Eclipse (Optional IDE)
• Netbeans (Optional IDE)
• IntelliJ IDEA (Optional IDE) -> send me an email for the academic license key (1 year - Maranatha Christian University)

Slide

• Introduction