BITS WILP Data Structures and Algorithms Design Handout 2017-H1
BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI
WORK INTEGRATED LEARNING PROGRAMMES
Digital Learning
Part A: Course Design
|
Course Title
|
Data
Structures and Algorithms Design
|
|
Course No(s)
|
SS
ZG519
|
|
Credit Units
|
5
|
|
Credit Model
|
|
|
Content Authors
|
A
Baskar
|
Course Objectives
|
CO1
|
Introduce mathematical and experimental techniques to analyze
algorithms
|
|
CO2
|
Introduce linear and non-linear data structures and best
practices to choose appropriate data structure for a given application
|
|
CO3
|
Exposes students to various sorting and searching
techniques
|
|
CO4
|
Overview of algorithm design methods such as the greedy
method, divide and conquer, dynamic programming, backtracking, and branch and
bound
|
|
CO5
|
Introduce complexity classes and ways of classifying problem.
|
Text Book(s)
|
T1
|
Algorithms
Design: Foundations, Analysis and Internet Examples Michael T. Goodrich,
Roberto Tamassia, 2006, Wiley (Students Edition)
|
Reference Book(s) & other resources
|
R1
|
Data Structures,
Algorithms and Applications in C++, Sartaj Sahni, Second Ed, 2005,
Universities Press
|
|
R2
|
Introduction to
Algorithms, TH Cormen, CE Leiserson, RL Rivest, C Stein, Third Ed, 2009, PHI
|
|
R3
|
Algorithm
Design, Jon Kleinberg, Eva Tardos, First Ed.,
Pearson
|
Content Structure
1.
Analyzing Algorithms [4
Hours]
1.1.
Theoretical Foundation
1.1.1.
Algorithms and it’s Specification
1.1.2.
Random Access Machine Model
1.1.3.
Counting Primitive Operations
1.1.4.
Notion of best case, average case and worst case
1.2.
Characterizing Run Time
1.2.1.
Use of asymptotic notation
1.2.2.
Big-Oh Notation, Little-Oh, Omega and Theta Notations
1.3.
Correctness of Algorithms
1.4.
Analyzing Recursive Algorithms
1.4.1.
Recurrence relations
1.4.2.
Specifying runtime of recursive algorithms
1.4.3.
Solving recurrence equations
1.5.
Case Study: Analyzing Algorithms
2.
Elementary Data
Structures [2 hours]
2.1.
Stacks
2.1.1.
Stack ADT and Implementation
2.1.2.
Applications
2.2.
Queues
2.2.1.
Queue ADT and Implementation
2.2.2.
Applications
2.3.
List
2.3.1.
Notion of position in lists
2.3.2.
List ADT and Implementation
3.
Non-Linear Data Structures [3 hours]
3.1.
Trees
3.1.1.
Terms and Definition
3.1.2.
Tree ADT
3.1.3.
Applications
3.2.
Binary Trees
3.2.1.
Properties
3.2.2.
Representations (Vector Based and Linked)
3.2.3.
Binary Tree traversal (In Order, Pre Order, Post Order)
3.2.4.
Applications
3.3.
Heaps
3.3.1.
Definition and Properties
3.3.2.
Representations (Vector Based and Linked)
3.3.3.
Insertion and deletion of elements
3.3.4.
Heap implementation of priority queue
3.3.5.
Heap sort
4.
Dictionaries [as Hash Tables and Search Trees] [3 hours]
4.1.
Unordered Dictionary
4.1.1.
ADT Specification
4.1.2.
Applications
4.2.
Hash Tables
4.2.1.
Notion of Hashing and Collision (with a simple vector based hash
table)
4.2.2.
Hash Functions
4.2.2.1.
Properties
4.2.2.2.
Simple hash functions
4.2.3.
Methods for Collision Handling
4.2.3.1.
Separate Chaining
4.2.3.2.
Notion of Load Factor
4.2.3.3.
Rehashing
4.2.3.4.
Open Addressing [ Linear & Quadratic Probing, Double
Hash]
4.3.
Ordered Dictionary
4.3.1.
ADT Specification
4.3.2.
Applications
4.4.
Binary Search Tree
4.4.1.
Motivation with the task of Searching and Binary Search
Algorithm
4.4.2.
Properties of BST
4.4.3.
Searching an element in BST
4.4.4.
Insertion and Removal of Elements
4.4.5.
Performance
5.
Algorithm Design Techniques [8 Hours]
5.1.
Greedy Method
5.1.1.
Design Principles and Strategy
5.1.2.
Fractional Knapsack Problem
5.1.3.
Task Scheduling Problem
5.2.
Divide and Conquer
5.2.1.
Design Principles and Straegy
5.2.2.
Analyzing Divide and Conquer Algorithms
5.2.3.
Integer Multiplication Problem
5.2.4.
Sorting Problem
5.2.4.1.
Merge Sort Algorithm
5.2.4.2.
Quick Sort Algorithm
5.2.5.
Searching Problem and
Binary Search Algorithm [Ref to 4.4.1]
5.3.
Dynamic Programming
5.3.1.
Design Principles and Strategy
5.3.2.
Matrix Chain Product Problem
5.3.3.
0/1 Knapsack Problem
5.4.
Graph Algorithms
5.4.1.
Introduction to Graphs
5.4.2.
Prim's and Kruskal's Algorithms [Greedy]
5.4.3.
Dijkstra’s Algorithm [Greedy]
5.4.4.
Bellman-ford Shortest Path Algorithm [Greedy]
5.4.5.
All Pair Shortest Path Algorithm [Dynamic Programming]
6.
Complexity Classes
[2 hours]
6.1.
Definition of P and NP
classes and examples
6.2.
Understanding NP-Completeness
Learning Outcomes:
|
No
|
Learning Outcomes
|
|
LO1
|
Analyzing algorithms using recurrence relations and expressing
it using asymptotic notation.
|
|
LO2
|
Understanding different sorting and searching algorithms with
the analysis of best, worst and average cases.
|
|
LO4
|
Understanding of graph algorithms for Reachability and Path
Finding
|
|
LO3
|
Students will be able to solve problems using appropriate data
structures to implement solutions.
|
|
L05
|
Understanding complexity classes P and NP
|
Part B: Contact Session Plan
|
Academic Term
|
Second Semester 2016-2017
|
|
Course Title
|
Data Structures and Algorithms
Design
|
|
Course No
|
SSZG 519
|
|
Content Developer
|
BHARAT M DESHPANDE
|
Glossary of Terms:
1.
Contact Hour (CH) stands for a hour long live session with
students conducted either in a physical classroom or enabled through
technology. In this model of instruction, instructor led sessions will be for
20 CH.
a.
Pre CH = Self Learning done prior to a given contact hour
b.
During CH = Content to be discussed during the contact hour by
the course instructor
c.
Post CH = Self Learning done post the contact hour
2.
RL stands for Recorded Lecture or Recorded Lesson. It is
presented to the student through an online portal. A given RL unfolds as a sequences
of video segments interleaved with exercises
3.
SS stands for Self-Study
to be done as a study of relevant sections from textbooks and reference books.
It could also include study of external resources.
4.
LE stands for Lab Exercises
5.
HW stands for Home Work will consists could be a selection of
problems from the text.
Contact
Hour 1
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL1.1
|
|
|
|
During CH
|
CH1
|
CH1.1= Introduction
CH1.2 = Algorithms and it’s Specification,
CH1.3 = Random Access Machine Model, Counting Primitive
Operations
CH1.4= Notion of best case, average case and worst case
|
T1: 1.1.1-1.1.3
|
|
Post CH
|
SS1
|
|
|
|
Post CH
|
HW1
|
|
|
|
Post CH
|
LE1
|
|
|
|
Post CH
|
QZ1
|
|
|
Notes:
Contact
Hour 2
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL1.1
|
|
|
|
During CH
|
CH2
|
CH2.1= Notion of best case, average case and worst case
CH2.2 =Use of asymptotic notation (Big-Oh Notation, Little-Oh,
Omega and Theta Notations)
|
T1: 1.2
|
|
Post CH
|
SS2
|
T1
– 1.3
|
|
|
Post CH
|
HW2
|
T1
- R-1.15, R-1.19
|
|
|
Post CH
|
LE2
|
|
|
|
Post CH
|
QZ2
|
|
|
Notes:
Contact
Hour 3
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH3
|
CH3.1 = Correctness of Algorithms
CH3.2= Analyzing
Recursive Algorithms:
CH3.3= Recurrence
relations, CH3.3= Specifying runtime of recursive algorithms,
|
T1: 1.1.4, Class Notes
|
|
Post CH
|
SS3
|
|
|
|
Post CH
|
HW3
|
|
|
|
Post CH
|
LE3
|
|
|
|
Post CH
|
QZ3
|
|
|
Notes:
Contact
Hour 4
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH3
|
CH4.1= Solving
recurrence equations
|
T1: 1.1.4, Class Notes
|
|
Post CH
|
SS3
|
|
|
|
Post CH
|
HW3
|
|
|
|
Post CH
|
LE3
|
|
|
|
Post CH
|
QZ3
|
|
|
Contact
Hour 5
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL1.2
|
|
|
|
During CH
|
CH4
|
CH4.1 =Stacks: ADT and Implementation, Applications
CH4.2= Queues: Queue ADT and Implementation, Applications
|
T1: 2.1
|
|
Post CH
|
SS4
|
|
|
|
Post CH
|
HW4
|
|
|
|
Post CH
|
LE4
|
|
|
|
Post CH
|
QZ4
|
|
|
Notes:
Contact
Hour 6
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL1.2
|
|
|
|
During CH
|
CH5
|
CH6.1 =List: Notion of position in lists
CH6.2 = List ADT and Implementation
|
T1: 2.2
|
|
Post CH
|
SS5
|
|
|
|
Post CH
|
HW5
|
T1
- R-2.1
|
|
|
Post CH
|
LE5
|
|
|
|
Post CH
|
QZ5
|
|
|
Notes:
Contact
Hour 7
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL1.3
|
|
|
|
During CH
|
CH7
|
CH7.1 =Binary Trees :
Representations (Vector Based and Linked),
C H7.2= Binary Tree traversal (In Order, Pre Order, Post
Order), CH7.3= Applications
|
T1: 2.3.3
|
|
Post CH
|
SS7
|
|
|
|
Post CH
|
HW7
|
|
|
|
Post CH
|
LE7
|
|
|
|
Post CH
|
QZ7
|
|
|
Notes:
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL2.2
|
|
|
|
During CH
|
CH8
|
CH8.1 =Heaps: Definition and Properties,
CH8.2 = Representations (Vector Based and Linked), CH8.3
=Insertion and deletion of elements
|
T1:2.4.1,2.4.2, 2.4.3
|
|
Post CH
|
SS8
|
|
|
|
Post CH
|
HW8
|
|
|
|
Post CH
|
LE8
|
|
|
|
Post CH
|
QZ8
|
|
|
Notes:
Contact
Hour 9
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL2.2
|
|
|
|
During CH
|
CH9
|
CH9.1 =Heap implementation of priority queue,
CH9.2 = Heap sort
|
T1:2.4.1,2.4.2, 2.4.3
|
|
Post CH
|
SS9
|
T1 - Section 2.4.2 PQ-Sort
|
|
|
Post CH
|
HW9
|
|
|
|
Post CH
|
LE9
|
|
|
|
Post CH
|
QZ9
|
|
|
Notes: Syllabus for mid-semester (Feb 2017)
1. Analyzing Algorithms
1.1. Theoretical Foundation
1.2. Characterizing Run Time
1.3. Correctness of Algorithms
1.4. Analyzing Recursive
Algorithms
2. Elementary Data Structures
2.1. Stacks
2.2. Queues
2.3. List
3. Non-Linear Data Structures
3.1. Trees
3.2. Binary Trees
3.3. Heaps
3.4. Sorting algorithms: Insertion
sort, Selection Sort, Heap Sort
4. Dictionaries
4.1. Dictionary ADT
4.2. Log file and Look-up table
4.3. Binary Search Tree
Contact
Hour 10
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL3.1
|
|
|
|
During CH
|
CH10
|
CH10.1 =Unordered Dictionary :ADT, Applications
CH10.2= Hash Tables: Notion of
Hashing and Collision (with a simple vector based hash table)
CH10.3 = Hash Functions: Properties, Simple hash functions
|
T1: 2.5.1, 2.5.2, 2.5.3, 2.5.4
Chapter 11 (Hash Tables) –
Intro to Algorithms (Cormen, 3e, 2010)
|
|
Post CH
|
SS10
|
|
|
|
Post CH
|
HW10
|
|
|
|
Post CH
|
LE10
|
|
|
|
Post CH
|
QZ10
|
|
|
Notes:
Contact
Hour 11
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL3.2
|
|
|
|
During CH
|
CH11
|
CH11.1 =Methods for Collision Handling:
CH11.2 = Notion of Load Factor,
CH11.3 = Rehashing,
CH11.4 = Open Addressing
|
T1: 2.5.5
Chapter 11 (Hash Tables) –
Intro to Algorithms (Cormen, 3e, 2010)
|
|
Post CH
|
SS11
|
|
|
|
Post CH
|
HW11
|
|
|
|
Post CH
|
LE11
|
|
|
|
Post CH
|
QZ11
|
|
|
Notes:
Contact
Hour 12
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL4.1
|
|
|
|
During CH
|
CH12
|
CH12.1= Ordered Dictionary:
ADT, Applications
CH12.2 = Binary Search Tree:
Motivation with the task of Searching and Binary Search Algorithm, CH12.3 =
Properties of BST
CH12.4 = Searching an element
in BST, Insertion and Removal of Elements
|
T1: 3.1.1-3.1.5
|
|
Post CH
|
SS12
|
T1: 3.1.6
|
|
|
Post CH
|
HW12
|
|
|
|
Post CH
|
LE12
|
|
|
|
Post CH
|
QZ12
|
|
|
Contact
Hour 13
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH13
|
CH13.1 =CH12.1 =Greedy Method: Design Principles and Strategy,
CH12.2 =Fractional Knapsack Problem
|
T1: 5.1.1
|
|
Post CH
|
SS13
|
|
|
|
Post CH
|
HW13
|
|
|
|
Post CH
|
LE13
|
|
|
|
Post CH
|
QZ13
|
|
|
Notes:
Contact
Hour 14
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH14
|
CH14.1 =Greedy Method Task Scheduling Problem
|
T1:5.1.2
|
|
Post CH
|
SS14
|
|
|
|
Post CH
|
HW14
|
|
|
|
Post CH
|
LE14
|
|
|
|
Post CH
|
QZ14
|
|
|
Notes:
Contact
Hour 15
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL2.1
|
|
|
|
During CH
|
CH15
|
CH15.1 =Divide and Conquer: Design Principles and Strategy,
CH15.2 = Analyzing Divide and Conquer Algorithms CH15.3 = Integer Multiplication Problem
|
T1:5.2.1, 5.2.2
|
|
Post CH
|
SS15
|
|
|
|
Post CH
|
HW15
|
|
|
|
Post CH
|
LE15
|
|
|
|
Post CH
|
QZ15
|
|
|
Notes:
Contact
Hour 16
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL2.1,RL2.2
|
|
|
|
During CH
|
CH16
|
CH16.1 = Merge Sort
CH16.2 =Quick Sort
|
T1:4.1, 4.3
|
|
Post CH
|
SS16
|
|
|
|
Post CH
|
HW16
|
|
|
|
Post CH
|
LE16
|
|
|
|
Post CH
|
QZ16
|
|
|
Notes:
Contact
Hour 17
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH17
|
CH17.1 =Dynamic Programming: Design Principles and Strategy,
CH17.2 = Matrix Chain Product Problem
CH17.3 =0/1 Knapsack Problem
|
T1: 5.3.1, 5.3.2
|
|
Post CH
|
SS17
|
|
|
|
Post CH
|
HW17
|
|
|
|
Post CH
|
LE17
|
|
|
|
Post CH
|
QZ17
|
|
|
Notes:
Contact
Hour 18
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL5.1,RL5.2
|
|
|
|
During CH
|
CH18
|
CH18.1 = Graphs : Terms
and Definitions, Properties, CH18.2 = Representations (Edge List, Adjacency
list, Adjacency Matrix)
CH18.3 = Graph Traversals
|
T1: 6.1, 6.2,6.3
|
|
Post CH
|
SS18
|
T1: 6.4
|
|
|
Post CH
|
HW18
|
|
|
|
Post CH
|
LE18
|
|
|
|
Post CH
|
QZ18
|
|
|
Notes:
Contact
Hour 19
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
RL 5.4,5.5
|
|
|
|
During CH
|
CH19
|
CH 19.1 =Single Source Shortest Path algorithm: Dijkstra’s
Algorithm
|
T1:7.1.1
T1: 13.1
|
|
Post CH
|
SS19
|
T1.7.1.2, 7.2.1, 7.3.1, 7.3.2
|
|
|
Post CH
|
HW19
|
|
|
|
Post CH
|
LE19
|
|
|
|
Post CH
|
QZ10
|
|
|
Notes:
Contact
Hour 20
|
Time
|
Type
|
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH20
|
CH20.1 = Definition of P and NP classes and examples
CH20.2 =Understanding NP-Completeness: CNF-SAT Cook-Levin
theorem
|
T
13.1, 13.2, T 13.3
|
|
Post CH
|
SS20
|
|
|
|
Post CH
|
HW20
|
|
|
|
Post CH
|
LE20
|
|
|
|
Post CH
|
QZ20
|
|
|
Notes:
Contact
Hour 21
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
During CH
|
CH21
|
CH21.1 =Polynomial time
reducibility: CNF-SAT and 3-SAT, Vertex Cover
|
T1:13.3
|
|
Post CH
|
SS21
|
Traveling
Salesman Problem
|
|
|
Post CH
|
HW21
|
|
|
|
Post CH
|
LE21
|
|
|
|
Post CH
|
QZ21
|
|
|
Notes:
Contact
Hour 22
|
Time
|
Type
|
Sequence
|
Content Reference
|
|
Pre CH
|
|
|
|
|
CH22
|
CH22.1 = Course Review
|
|
|
|
Post CH
|
SS22
|
|
|
|
Post CH
|
HW22
|
|
|
|
Post CH
|
LE22
|
|
|
|
Post CH
|
QZ22
|
|
|
Lab exercises
1 Find out what an Ackerman's function is and write a C/C++
recursive program to calculate the Ackerman's function for two positive
integers. What are the challenges That you see?
2 Representing polynomial in circular linked list, write a
C/C++ program to accept two polynomials, add them and display the sum.
3 Write a C/C++ program to simulate the working of a simple
LIFO stack of integers showing the operations: push and pop.
4 Write a C/C++ program to evaluate a valid postfix expression
using stacks. The arithmetic operators are + , -, *, / and use ^ or $ for
exponent operator.
5 Write a C/C++ program to simulate the working of a simple
FIFO character queue showing the operations: add, delete and display.
6 Write a C/C++ program to implement a circular queue of
integers. Do you experience any advantage of circular queue over linear queue?
7 Write a C/C++ program to take integers one at a time, create
a Binary Search Tree (BST) and display its preorder, inorder and postorder
traversals.
8 Write a C/C++ program to take integers one at a time, create
a max heap using array based implementation and display the array from left to
right.
9 Write C/C++ programs to perform the following to sort the
integers:
a.
Heap Sort.
b.
Merge Sort
c.
Quick Sort
Using time() or delay() library
functions, compare their performances.
10 Write iterative and recursive C/C++ versions of Binary
Search for searching an integer key from the given list of sorted integers
(increasing order).
11 Representing graphs in adjacency matrix, write a C/C++
program to find out the single source shortest path from a given source using
Dijkstra's Algorithm.
12 Representing graphs in adjacency matrix, write C/C++
programs:
a.
Single source shortest path from a given source using
Bellman-Ford Algorithm.
b.
All Source-Shortest paths using Floyd-Warshall
Algorithm.
Note:
provide some edges with negative costs and verify working.
13 Representing graphs in adjacency matrix, write a C/C++
program to solve the Travelling Salesman Problem (TSP) using a suitable
algorithmic approach.
14 There is a row of n coins whose values are some positive
integers c1, c2, . . . , cn, not necessarily distinct. The goal is to pick up
the maximum amount of money F(n), subject to the constraint that no two coins
adjacent to each other can be picked up. Formulate the Dynamic Programming
Approach, write a C/C++ program and verify your output.
15 Accept cost in integers for n jobs when they are assigned
to n different people. Using Branch and Bound strategy, write a C/C++ program
to find out an optimum job assignment with minimum cost. A job cannot be
assigned to two people and one person cannot have more than one job.
16 Using backtracking approach, write a C/C++ program to print
the permutations of the characters of a string. E.g. For ABC, the different
possibilities are ABC, ACB, BAC, BCA, CAB and CBA.
17 Formulate dynamic programming for 0/1 Knapsack, write C/C++
program for it and measure its timing performance with the different inputs
Assignments:
Problem-1
Suppose
you are hired as a consultant to a professor, Dr. Bob Loblaw, from the
Sociology department. He is asking that you build him a software system that
can maintain a set, P , of people from a country, Phishnonia, that he is
studying. People in Phishnonia are free to come and go as they please, so Dr.
Bob Loblaw is asking that your system support fast insertions and deletions. In
addition, he is also interested in doing queries that respectively return the
mean and median ages of the people in P . His thesis is that if the median age
is much smaller than
the
mean, then the Phishnonia is ripe for revolution, for it implies that there are
a disproportionate number of young people. Describe a scheme for maintaining P
that can support median and mean age queries, subject to insertions and
removals, with each of these operations running in at most O(log n) time, where
n is the number of people in P .
Problem-2
Suppose
there is a computer game, LoC, where a player moves through a three-dimensional
world defined by the cells in an n × n × n array, C. Each cell, C[i, j, k],
specifies the number of points that a player in LoC gets when they are at
position (i, j, k). At the start of a game in LoC, there are only
O(n)
nonzero cells in C; all the other O(n3 ) cells in C are equal to 0.
During the course of the game, if a player moves to a position (i, j, k) such
that C[i, j, k] is nonzero, then all the points in C[i, j, k] are awarded to
the player and the value of C[i, j, k] is reduced to 0. Then the game picks
another position, (i’, j’ , k’ ), at random and adds 100 points to C[i’ , j’ ,
k’ ]. The problem is that this game was designed for playing on a large
computer and now must be adapted to run on a smartphone, which has much less
memory. So you cannot afford to use O(n3 ) space to represent C, as
in the original version. Describe an efficient way to represent C, which uses
only O(n) space. Also describe how to lookup the value of any cell, C[i, j, k],
and how to add 100 points to any cell, C[i, j, k], efficiently so that looking
up the value of any cell, C[i, j, k], can be done in O(log n) worst-
case
time or better
Problem-3
The
pointy-haired boss (PHB) of an office in a major technology company would like
to throw a party. Based on the performance reviews he has done, the PHB has
assigned an integer “fun factor” score, F (x), for each employee, x, in his
office. In order for the party to be as crazy as possible, the PHB has one
rule: an employee, x, may be invited to the party only if x’s immediate
supervisor is not invited. Suppose you are the PHB’s administrative assistant,
and it is your job to figure out who to invite, subject to this rule, given the
list of F (x) values and the office organizational chart, which is a tree, T ,
rooted at the PHB, containing the n employees as nodes, so that each employee’s
parent in T is the immediate supervisor of that employee. Describe an algorithm
for solving this office party problem, by choosing a group of employees to
invite to the party such that this group has the largest total fun factor while
satisfying the PHB’s rule and also guaranteeing that you are invited, which, of
course, means that the PHB is not. What is the running time of your algorithm?
Notes:
Evaluation Scheme:
Legend: EC =
Evaluation Component; AN = After Noon Session; FN = Fore Noon Session
|
No
|
Name
|
Type
|
Duration
|
Weight
|
Day, Date, Session, Time
|
|
EC-1
|
Quiz-I/ Assignment-I
|
Online
|
-
|
5%
|
February
1 to 10, 2017
|
|
|
Quiz-II
|
Online
|
-
|
5%
|
March
1 to 10, 2017
|
|
|
Quiz-III
|
Online
|
-
|
5%
|
March
20 to 30, 2017
|
|
|
Lab
|
Online
|
|
10%
|
To be
announced
|
|
EC-2
|
Mid-Semester Test
|
Closed Book
|
2 hours
|
30%
|
25/02/2017 (AN) 2 PM – 4 PM
|
|
EC-3
|
Comprehensive Exam
|
Open Book
|
3 hours
|
45%
|
08/04/2017 (AN 2 PM – 5 PM
|
Syllabus for
Mid-Semester Test (Closed Book): Topics in Session Nos. 1 to 11
Syllabus for
Comprehensive Exam (Open Book): All topics (Session Nos. 1 to 22)
Important
links and information:
Elearn portal: https://elearn.bits-pilani.ac.in
Students are
expected to visit the Elearn portal on a regular basis and stay up to date with
the latest announcements and deadlines.
Contact sessions: Students should
attend the online lectures as per the schedule provided on the Elearn portal.
Evaluation Guidelines:
1.
EC-1 consists of either two Assignments or three Quizzes.
Students will attempt them through the course pages on the Elearn portal.
Announcements will be made on the portal, in a timely manner.
2.
For Closed Book tests: No books or reference material of any
kind will be permitted.
3.
For Open Book exams: Use of books and any printed / written
reference material (filed or bound) is permitted. However, loose sheets of
paper will not be allowed. Use of calculators is permitted in all exams.
Laptops/Mobiles of any kind are not allowed. Exchange of any material is not
allowed.
4.
If a student is unable to appear for the Regular Test/Exam due
to genuine exigencies, the student should follow the procedure to apply for the
Make-Up Test/Exam which will be made available on the Elearn portal. The
Make-Up Test/Exam will be conducted only at selected exam centres on the dates
to be announced later.
It shall be the
responsibility of the individual student to be regular in maintaining the self
study schedule as given in the course handout, attend the online lectures, and
take all the prescribed evaluation components such as Assignment/Quiz,
Mid-Semester Test and Comprehensive Exam according to the evaluation scheme
provided in the handout.
good job
ReplyDelete