Final tips on the final exam

I modified the weighting of questions.  This is the new arrangement:-

Question 1 - 14 marks :: On chapter 6 content

Choose EITHER Question 2 OR Question 3

Question 2 - 16 marks :: On chapter 7 content

Question 3 - 16 marks :: On chapter 8 content

==============

TIPS

1- Make sure you can solve a Knapsack/TSP-type problem quickly so that you can free yourself up for the other questions.

2- Question 3 is very hard.   (This is the 'write an algorithm' question.)  Only attempt this if you absolutely do not want to do Question 2.  

Last year's exam

Here it is - the equations have been messed up.  Try downloading instead of displaying within google docs - may improve situation.

I got an A because ...

Ahmed Shihab

Blah Blah Blah

Professor Viktor Grishin
Algorithms II Instructor
My Former University

29 May 2012

Dear Professor Grishin,

I am writing to you almost a year after you taught us Algo2.  I thought I'd write you a letter to say Hello and to say that I really had deserved that A in the practical component of Algos2!

In the year that has passed, I have since worked with a small company (TikTok Ltd) where I am a developer.  I am not only focused on coding, I also do bits of research. The grounding I had in Algos2, with all the tracing, the coding, the exposure to ideas and solution methods has helped a lot.

I can't lie to you and say that I use any of the algorithms we studied, but I think it's all about the influence it had on my approach and on my thinking.  I am glad I got that A because it makes me feel that I have proof of that influence.  If I'd gotten only a C, it would be hard to convince people that the course made such an impression on me.

The influence comes out in small but significant ways.  I always brainstorm ideas, and I look for templates to base my work on.  I write algorithms first, code later.  I trace through my algorithm, making sure that my initial idea is right.  Then begins the implementation, which is often tiring and time-consuming.  After I have a running program, I try a different approach, to see if I can come up with a better algorithm.  It is a rigorous effort; but I am somehow able to cope with it all - because of those days I spent working on our practical assignments.

Thank you so much for all your efforts. Do you mind if I pop by your office soon to say hello?

Yours sincerely,
Ahmed Shihab

Practical Coursework

Everyone will get an A in this component of your course (i.e., you will obtain a mark between 18-20, out of 20).

I want you to write a letter to me dated 29 May 2012 explaining why you got an A in your practical component of the Algo2 course.  Do not praise your coding/algos/computer-science accomplishments (although that is allowed), instead explain how you developed as a person over the year and who you have become.  Write the letter, despite the future date, in the past tense.

Deadline: 29th May 2011.

Rules:

1. Use at least 100 words.
2. Absolutely no copying.  I want sincere, individual essays.
3. You deserve that A, now explain why.

The letter shall start:

I got an A in the practical component of Algo2 because ...

Midterm update

I have had a full briefing re Algo2 complaints. Some unreasonable complaints were made, also reasonable ones.

Good decisions were taken: Sudoku Q will now be a bonus question. The trace Q will be 15, the edge-colors Q will be 10.

I've had a look at your papers. The new marking scheme would put most ppl around 15 marks.

The 15 marks for the assignment remain outstanding. The deadline is a very strict 17th April. Make use of the 15 marks.

prep for the mids

Last year's 5th

Last year's midterm

Past midterms

Pre-midterm project

• Each team will pick one of these projects.  
• No two teams may do the same project.  
• A team will consist of 4-5 members.

USE BACKTRACKING TO IMPLEMENT AN ALGORITHMIC SOLUTION TO ONE OF THE PROBLEMS BELOW:

1. 3D n-Queens - find all possible solutions in an n x n x n grid
2. 0-1 Knapsack problem - this is a standard problem
3. Minimum Spanning Tree problem - this is a standard problem
4. Single-source shortest paths problem - find the shortest paths from a given vertex to all the others.
5. * Travelling Salesman problem - find the minimum-cost cycle in an undirected, weighted graph.
6. * Sudoku solver

Projects marked with a * are challenging.  I recommend strong teams to do them.  

Write a comment on this post in order to book a project.  Allocation of projects will be first-come, first-served.

All projects will submit a Java or C++ application that takes the inputs of the problem and demonstrates the correct outputs.  Extra marks if your application has a relatively user-friendly graphical interface (instead of it being an unexciting console application).

GUIDE

• Read up on your problem in the books I provided (especially the Skiena book)
• Read up on the problem on the internet
• Write source code to implement your solution.  Remember I am interested in backtracking solutions only.
• Play with your software, test it.  Be ready to answer questions on it.

Please book a slot with me to demonstrate the application.  I want everyone to have done the demonstration by 10th April or very soon afterwards.

Marks will be allocated based on:

- successful completion of project

- comprehension of problem

- performance during the demo

Team-member marks will vary depending on ability to answer questions during the demo.