Scribd
Upload
38 views1 page

Computer Science Department

This document contains an exam for an operating systems course. It asks students to analyze the time complexity of three nested loop algorithms and provides sample code. It also asks students to implement and compare the running time of brute force and divide-and-conquer algorithms to find the maximum sum of subsequent elements in a number sequence.

Uploaded by

Christopher Miller
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
38 views1 page

Computer Science Department

This document contains an exam for an operating systems course. It asks students to analyze the time complexity of three nested loop algorithms and provides sample code. It also asks students to implement and compare the running time of brute force and divide-and-conquer algorithms to find the maximum sum of subsequent elements in a number sequence.

Uploaded by

Christopher Miller
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Notre Dame University-Louaize

Computer Science Department


CSC 414 Operating Systems
Exam 1, Fall 2012
1. What is the complexity of
1
2
3
4
5
6
7

f o r ( i =1; i<=n ; i ++){


j =1;
while ( j < i ){
j =2;
sum+=1;
}
}

2. What is the complexity of


1
2
3
4
5
6
7
8

i n t i , j , k , count =0;
f o r ( i =1; i<=n ; i ++){
f o r ( j =1; j<=n ; j ++){
f o r ( k=1;k<=n ; k =2)[
count++;
}
}
}

3. What is the complexity of


1
2
3
4
5
6
7
8

i n t i , j , k , count =0;
f o r ( i =1; i<=n ; i ++){
f o r ( j =1; j<=n ; j =2){
f o r ( k=1;k<=n ; k =2)[
count++;
}
}
}

4. Write a C++ implementation of the two solutions for the max subsequent sum problem
( brute force and the divide-and-conquer). Use your C++ implementation to compute
the max subsequent sum of the provided input (a column of numbers where the first one
denotes the total number of entries in the sequence and the remaining ones are the values
of the elements of the sequence). What is the running time of each implementation?

You might also like