CST 306 Algorithm Analysis and Design




Syllabus
.html                              .pdf
Students' List
S6D
17/5 s6d


Contact  Hours


19/04/22
2/5
10/5
16/5
25/5
20/6
Monday

2
3

3
3
Tuesday
4
1
4


Wednesday 4
1
1
1
1
Thursday
1, 4 4
4
4
4
6
Friday
2, 6
4

2
1
1

Progress
Course Progress Page
Assignments
24/6: Class assignment 1 (CA1) is scheduled for 30/6/22, 3PM to 4PM.
Answer the following sample questions in maximum three A4 sheets and may be carried to the test hall.
A variant of the sample questions will be asked for the CA1.
Answer these questions neatly and precisely.
White papers for writing the CA should be brought by the students.
Twine or stapler for tieing the answer sheets will be arranged.

Questions
(1) Apply the SCC algorithm discussed in class(written down the page) to find the SCCs of the graph with directed edges BA, CA, BC, CD, DB

(2) Apply the topological sorting algorithm with queue discussed in class on the following graph with directed edges BA, BD, DC, CA.

(3) Draw a BST with minimum height with node values 10 20 30 40 50 60 70.
Then using AVL approach,  insert into that tree the following values one by one: 45 55 75 53

29/6: If placement drive test is happening tomorrow, CA1 will be postponed.

6/7: CA1 is scheduled for 7/7/22, 3PM to 4PM

20/7: CA1 marks

25/7: CA2 will be conducted on 27/7 Wednesday.
Question will be to solve TSP using branch and bound approach with 5 vertices.

Tips: To neglect columns you can use multiple pens placed vertically on the matrix written  more spaciously  on the paper - instead of repeatedly rewriting the marked matrix.

In case of a tie use the deeper node to explore further.

The vertices will be marked as 1, 2, 3, 4, 5.
So can have an idea about what will be the branching edges for each level in advance.

Permitted to carry the solution to the problem discussed in class in a single sheet.
26/7: CA2
Question paper structure is posted. The adjacency matrix and values of x and y will be available in the QP. For some cells x and y are to be replaced by actual values.

Your KTU register number is required to calculate y. So note down it on top of the answer paper.
Fill whatever details required in the answer sheets like name and roll number in advance to save time.

You need not draw the graph to solve this problem. So it is not required. If it helps you, then you may draw it.

Permitted to carry one sheet of A4 size paper with the illustration of the solution discussed in class. You have to bring the writing papers. Stapler will be arranged. Not permitted to carry mobile, bag, books etc.

CA2 will be conducted from 9AM to 10AM on 27/7/22.

Venue
Roll #s 01 - 33: Room # 303
Roll #s 34 - 68: Room # 301
-------
27/7: Utterly disappointed with the CA2 performance.
CA2 Marks



Tests
18/6:  T1 evaluations have been completed. Marks are here.
Answer keys and marks scheme will be discussed during next class session.
Some answers are marked as "explain" - meaning that the marks if eligible will be awarded after listening to the students.
Others also with claims about their marks could discuss with proper arguments.
So for that, be well prepared about the questions and answers.
Requests like "could you explain where I lost marks so that I can improve next time" will not be entertained normally.
All of you are requested to check the answer papers and ensure that you get rewarded with the marks you are eligible for.
Emails in this regard also will not be entertained for the time being as personal interactions are required to discuss queries if any properly.

21/7: T2: During class session on 18/7 "Kruskal complexity - Not covered during T2 period"  concern was raised. It was covered during T1 with mention about the future. Also it was part of the topics discussed during T2. Anyway, 2.5 marks will be awarded to all in addition to the total marks obtained for T2.

22/7: T2 marks

1/8: T1 Quick-sort: To cover quick sort related confusion 5 marks will be awarded, if you have appeared for T1.
T2: Kruskal issue - 2.5 marks will be awarded, if you have appeared for T2.

2/8: Retest marks
Sessional
1/8/22 (Updated on 2/8/22 after retest)
Draft Sessional is ready.
T1 booster: up to 6 marks
T2 booster: up to 4 marks
A1 booster: up to 3 marks
A2 booster: up to 3 marks
Attendance component: att_percentage/10 +1

Entries per line:
rn t1/12.5 t2/12.5 a1/9 a2/6 at% --> t1+6 t2+4 a1+3 a2+3 at ---> actual boosted rounded

3/8/22:
KTU Sessional and attendance entry are here. It will be submitted tomorrow.
Mistakes if any may be reported.
Attendance shortage matter may be taken up with staff advisor and college authorities.

4/8: One attendance shortage entry exists. Candidate may seek whatever recourse options available at his disposal. This entry is corrected to two decimal places from the rounded figure.

Doubt clearing
Attendance Students are expected to attend all the classes. Please be at the class at the time of commencement.

Attendance shall be marked only if physically present in the class. As per KTU rules, absence for all activities and contingencies should be limited to 25%.

Also, late comers will be marked, and two late marks will count as one absence.

1/6/22 - Attendance % as of now
Those below 75%
67 13   72
57 13   72
47 13   72
42 13   72
10 13   72
26 12   67
9 11   61
5 11   61
30 11   61
54 10   56
28 10   56
49 8   44
55 7   39

1/7/22 - Attendance % as of now
Those below 75%
58 20   74
57 20   74
42 20   74
30 20   74
5 19   70
9 18   67
54 18   67
28 18   67
55 16   59
49 15   56

(Updated from 27/7 - frequently)
1/8 - Attendance % as of now
Those below 75%
49 28   66

As per attendance rules, 8.3, attendance up to  5% can be considered for college level duty leave. Hence maximum two hours/student 5% will be considered.

Requests received so far and considered.
10 - 1 hour
28 - 5%
32 - 2 hours
39 - 1
47 - 5%
49 - 5%
54 - 5%
(Will be updated in the attendance statement soon)

2/8:
Att % after considering duty leaves as well. This data is used for sessional computation as well.
Additional content
Approximate Graph colouring algorithms
(1) Simple greedy algorithm:
    - Starting an arbitrary node, colour each node with a colour not used by its neighbours.

(2) Largest-degree-first algorithm
   - Same as above but start with largest degree node

(3) Dsatur algorithm
   - same as (1) above, but start with node with largest saturation.
   - (Vertex saturation: No. of unique colours used by neighbours)

(4)Wigderson's algorithm
 - 3 colourable graphs can be coloured with at most O(n\sqrtn) colours
- Extensible to k-colouring

Algorithm for 3-colourable graphs
G=(V,E) is 3-colourable
Wig(G)
{        i <-- 1; n <-- |V|
          while Δ(G)n\Delta(G) \ge \lceil \sqrtn \rceil
        {     v <-- maximum degree vertex
               H <-- subgraph with v's neighbours
               2-colour H with i, i+1
               colour v with i+2
               i+ <-- 2
               Delete v and H
          }
        Colour any remaining vertices with i, i+1, ... using largest-degree-first algorithm


}




\Delta(G) \ge \lceil \sqrtn \rceil




/Announcements/Information
1/8
Retests against T1 and T2 will be conducted on 3/8/22, at 10 - 12
CA1 second chance will be on  3/8/22,  at 2 - 3.

Appearance in all these will be restricted to those who missed the first chance due to genuine reasons and obtained prior permission.

Based on the request by the 3 eligible candidates T1 and T2 will be conducted tomorrow (2/8/22, Tuesday).

Subsequently CA1 second chance will be conducted at 2 -3 PM on 2/8/22.
13/7
Topics for T2:
Topics covered under Module 3 and 4.
Since SCC and topological sort are covered in CA1 they are excluded from T2.

Additional information for the matrix chain multiplication order algorithm.
Against each table entry store the value of k to figure out the optimal association.
6/7
CA1 is scheduled for 7/7 - 6th hour.
30/6
Today 6th hour we shall have a remedial session for those who are not attending the placement drive.
Those who have scored less than 20 marks in T1 is expected to attend it. Others can also attend.
There will be no regular class attendance. But attendance will be recorded and can be considered in case it will be beneficial to the student as part of regular attendance.
Those with doubts, or who require more explanation on any of the topics covered so far could  convey the doubt by email, in writing, or in person by 2PM today.
29/6 If placement drive test is happening tomorrow, CA1 will be postponed.
There won't be a class for the sake of attendance. Attendance will be recorded only if a class session is conducted.
24/6
Algorithm for SCC
1. Do DFS and push the farthest node on to a stack S and finally the starting node.
    Do this until all nodes are pushed. Do not push a visited node again.
2. Obtain the transpose of the graph.
3. Do DFS using the vertex popped out from S as starting node on the new graph.
    Starting node will produce one SCC.
    Subsequent nodes from S will be popped out, and will be used for further DFS operation if it is not already visited.
    Always avoid visited nodes.

Note: Use separate stack for the second DFS

7/6
T1 - Hope all will attend the test.
Retest will be a difficult affair.
6/6/22
Question pattern for T1
Answer all questions
Part A - 4 questions x 5 marks each = 20 marks
part B - 3 questions  x 10 marks each (may be with sub-sections) = 30 marks
Total 50 marks (2 hrs.).

Please write legibly, precisely, and completely. 
Ensure that question numbers are clearly visible on the margin side.
Please report and start in time, else you may not get sufficient time to answer properly.
6/5/22
For attendance, presently we are following the list suggested by the students with roll numbers from 1 to 67 and with permanent absentees 48, and 52.