IIIT Delhi - Computer Science Teachers Workshop Day 3

IIITD Workshop Day 3 Session V

Click to access PDF of the Presentation

OVERALL FEEDBACK IIITD Workshop for CS Teachers

IIITD Day 1 Solutions to Problems

	#include <iostream>
	#include <deque>
	using namespace std;
	// A Dequeue (Double ended queue) based method for printing maixmum element of
	// all subarrays of size k
	void printKMax(int arr[], int n, int k)
	{
	// Create a Double Ended Queue, Qi that will store indexes of array elements
	// The queue will store indexes of useful elements in every window and it will
	// maintain decreasing order of values from front to rear in Qi, i.e.,
	// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
	std::deque<int> Qi(k);
	/* Process first k (or first window) elements of array */
	int i;
	for (i = 0; i < k; ++i)
	{
	// For very element, the previous smaller elements are useless so
	// remove them from Qi
	while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
	Qi.pop_back(); // Remove from rear
	// Add new element at rear of queue
	Qi.push_back(i);
	}
	// Process rest of the elements, i.e., from arr[k] to arr[n-1]
	for ( ; i < n; ++i)
	{
	// The element at the front of the queue is the largest element of
	// previous window, so print it
	cout << arr[Qi.front()] << " ";
	// Remove the elements which are out of this window
	while ( (!Qi.empty()) && Qi.front() <= i - k)
	Qi.pop_front(); // Remove from front of queue
	// Remove all elements smaller than the currently
	// being added element (remove useless elements)
	while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
	Qi.pop_back();
	// Add current element at the rear of Qi
	Qi.push_back(i);
	}
	// Print the maximum element of last window
	cout << arr[Qi.front()];
	}
	// Driver program to test above functions
	int main()
	{
	int arr[] = {12, 1, 78, 90, 57, 89, 56};
	int n = sizeof(arr)/sizeof(arr[0]);
	int k = 3;
	printKMax(arr, n, k);
	cout << ("\n");
	return 0;
	}

view raw Solution21.cpp hosted with ❤ by GitHub

IIITD Workshop Day 2 Session IV

Dr. Debajyoti Bera (IIIT-Delhi) and Team Part 1 Click to download the PDF of Presentation
Part 2 Click to download the PDF of Presentation

IIIT Delhi - Computer Science Teachers Workshop Day 2

Share Day 2 Feedback

IIITD Workshop Day 2 Session III

Prof. Rajiv Raman, IIIT Delhi and Team
Click to download PDF of presentation

Revised Schedule for Day 3 - Open Session

IIIT Delhi Workshop for Computer Science Teachers
Day 3 Revised Schedule

Note: New Members are also WELCOME
DAY DATE: SATURDAY, 22nd AUGUST, 2015

TIME	SESSION
9:30-10:45	Intro to graphs and trees
10:45-11:00	Break
11:00-11:30	CS as a Discipline and what is done at University by Prof. Pankaj Jalote and Prof.Dheeraj Sanghi
11:30-11:50	Best practices in schools - A brif presentation
11:50-12:10	Projects - discussion on the compilation of projects
12:10-12:30	Contests for school students -Codechef
12:30 - 1:00	Open discussion (on what can be done for improving CS Education in schools)
01:00-01:30	Lunch
01:30 onwards	Round of IIIT Delhi and See Programmes at Esya

Problems of Day 1

Problems Day 1: 

Session 1

Problem 1:

You are given an m-bit message. Assume this is at locations 0 to m-1 in an array M. Write a program to compute the Hamming code corresponding to this message in an array S.

Problem 2:

You are given an n×n system of linear equations (n equations in n variables). Write a program to solve this system using Gaussian elimination (the method discussed in class).

Session 2

Problem 1:
Propose an O(n) time algorithm to find the largest element in every contiguous subarray of size k.

For example:
If the array is: {12, 1, 78, 90, 57, 89, 56} and k = 3.
The answer will be: 78, 90, 90, 90, 89

In this case, we find the maximum of elements with indices: (0,1,2), (1,2,3), (2,3,4), (3,4,5) and so on ...

The important point to note is that the time complexity should be independent of k. You can use auxiliary data structures such as stacks and queues.

Problem 2:
Assume that I have an unsorted array with n elements. Each element is an integer between 0 and (n-1). Propose an O(n) time algorithm for sorting this array.

Share Day 2 Feedback

IIIT Delhi - Computer Science Teachers Workshop Day 1

IIITD Workshop Day 1 Session II

Prof. Smruti Ranjan Sarangi

IIITD Workshop Day 1 Session I

Prof. Naveen Garg
IIT, Delhi

Note: Last Slide (Slide 17) of the presentation have the excercises for you.