Difference between revisions of "MSc: Optimization"

From IU
Jump to navigation Jump to search
Line 3: Line 3:
 
* <span>'''Course name:'''</span> Optimization
  
* <span>'''Course name:'''</span> Optimization
 
* <span>'''Course number:'''</span> R-01
  
* <span>'''Course number:'''</span> R-01
−  
−
== Course Characteristics ==
  
−  
−
* '''1. Key concepts of the class'''</span>
  
−
* <span>'''Year of instruction:'''</span> 3rd year of BS
  
−
* <span>'''Semester of instruction:'''</span> 2nd semester
  
−
* <span>'''No. of Credits:'''</span> 5 ECTS
  
−
* <span>'''Total workload on average:'''</span> 180 hours overall
  
−
* <span>'''Class lecture hours:'''</span> 2 per week.
  
−
* <span>'''Class tutorial hours:'''</span> 2 per week.
  
−
* <span>'''Lab hours:'''</span> 2 per week.
  
−
* <span>'''Individual lab hours:'''</span> 0.
  
−
* <span>'''Frequency:'''</span> weekly throughout the semester.
  
−
* <span>'''Grading mode:'''</span> letters: A, B, C, D.
  
−  
−
== Prerequisites ==
  
−  
−
Familiarity with multivariate calculus, elementary real analysis, and linear algebra.
  
−  
−
* Multivariate calculus
  
−
* Linear Algebra
  
−  
−
== Course outline ==
  
−  
−
This course studies fundamental concepts of optimization, which is the problem of making decisions to maximize or minimize an objective in the presence of constraints. The course takes a unified view of optimization and covers the main areas of application and the main optimization algorithms. It covers linear and nonlinear optimization.
  
−  
−
== Expected learning outcomes ==
  
−  
−
After this course, students will be able to:
  
−  
−
* be able to formulate problems in their fields of research as optimization problems
  
−
* be able to transform an optimization problem into its standard form
  
−
* understand how to assess and check the feasiblity and optimality of a particular solution to a general constrained optimization problem
  
−
* be able to use the optimality conditions to search for a local or global solution from a starting point.
  
−
* understand the computational details behind the numerical methods discussed in class, when they apply, and what their convergence rates are.
  
−
* be able to implement the numerical methods discussed in class and verify their theoretical properties in practice.
  
−
* be able to apply the learned techniques and analysis tools to problems arising in their own research.
  
−  
−
== Expected acquired core competences ==
  
−  
−
* Numerical analysis
  
−
* Numerical optimization
  
−  
−
== Detailed topics covered in the course ==
  
−  
−
* Linear Optimization
  
−
* Simplex Method
  
−
* Branch and Bound and Cutting planes
  
−
* Nonlinear Optimization
  
−  
−
== Textbook ==
  
−  
−
* C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
  
−
* D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
  
−  
−
== Reference material ==
  
−  
−
* Slides of the lectures
  
−
* Samples of examination questions
  
−  
−
== Required computer resources ==
  
−  
−
Matlab or Python.
  
−  
−
== Evaluation ==
  
−  
−
* Quizzes (0%)
  
−
* Labs (0%)
  
−
* Assignments (100% or 0%), i.e., as alternative to the final exam.
  
−
* Final Exam (0% or 100%), i.e., as alternative to the assignments.
  
−
* Class and lab participation (0%)
  
−  
−
= Operating Systems =
  
−  
−
Course name: Operating Systems<br />
  
−
Course number: R-01
  
   
 
== Course characteristics ==
  
== Course characteristics ==
Line 84: Line 8:
 
=== Key concepts of the class ===
  
=== Key concepts of the class ===
   
−
* Structure of an operating system
 +
* Optimization of a cost function
  +
* Algorithms to find solution of linear and nonlinear optimization problems
−
* Specific mechanisms, policies, and algorithms used to implement the different parts of an operating system
  
   
 
=== What is the purpose of this course? ===
  
=== What is the purpose of this course? ===
   
  +
The main purpose of this course to make the student aware of basic notions of mathematical programming and of its importance in the area of engineering.
−
Operating systems are the core part of a computing device and computing devices are an integral part of our life, not only as programmers, but also just as human being – it is enough to think at smart homes infrastructures, now available at accessible prices to everyone, at car devices, like smart navigator and cruise control systems, at other infrastructures. Therefore, a fundamental understanding of the structure of an operating systems has a paramount role in the curriculum of a student in computer science and engineering. The purpose of this course is to provide such understanding. This is a core course, so it is not among its goals to explore the details of the various proposal for operating systems that are now emerging: this is the subject of more advanced endeavours.
  
   
 
=== Course Objectives Based on Bloom’s Taxonomy ===
  
=== Course Objectives Based on Bloom’s Taxonomy ===
Line 97: Line 21:
 
By the end of the course, the students should be able to recognize and define:
  
By the end of the course, the students should be able to recognize and define:
   
  +
* explain the goal of some optimization problems
−
* fundamental components of an Operating Systems,
  
  +
* remind the importance of converge analysis for optimization algorithms
−
* organization of primary memory and the associated concept of virtual memory, with techniques based on paging and segmenting,
  
  +
* draft solution codes in Python/Matlab.
−
* structure of secondary memory (file systems),
  
−
* management of the processor(s) and of the connected scheduling algorithms,
  
−
* allocation of resources and the associated problems (deadlocks),
  
−
* approaches to handle I/O.
  
   
 
==== What should a student be able to understand at the end of the course? ====
  
==== What should a student be able to understand at the end of the course? ====
Line 108: Line 29:
 
By the end of the course, the students should be able to describe and explain (with examples):
  
By the end of the course, the students should be able to describe and explain (with examples):
   
  +
* formulate a simple optimization problem
−
* strategies and algorithms for allocating processor(s) time to processes,
  
  +
* select the appropriate solution algorithm
−
* strategies and algorithms for allocating primary memory to processes,
  
  +
* find the solution.
−
* the fundamental states of a process and how they are reached,
  
−
* concept and implementation of the address space of a process, both in the single threaded and in the multi threaded cases.
  
−
* techniques to organize files and directories in secondary memory,
  
−
* algorithms for a safe concurrent access to resources, preventing or avoiding deadlocks,
  
−
* methods for attaching different kind of devices to a computer, also considering different kind of buses.
  
   
 
==== What should a student be able to apply at the end of the course? ====
  
==== What should a student be able to apply at the end of the course? ====
Line 120: Line 37:
 
By the end of the course, the students should be able to apply:
  
By the end of the course, the students should be able to apply:
   
  +
* the simplex method
−
* strategies for programming at the Operating System level,
  
  +
* algorithms to solve nonlinear optimization problems.
−
* fundamental system calls for process creation, termination,
  
−
* fundamental system calls to allocate, change, and deallocate primary memory to processes,
  
−
* libraries to handle buffered and unbuffered interconnections with the computer, including files and I/O devices,
  
−
* the identification of the most suitable algorithms for process, memory, and I/O management depending on the context in which their target operating system is working.
  
   
 
=== Course evaluation ===
  
=== Course evaluation ===
Line 143: Line 57:
 
|-
  
|-
 
| Labs/seminar classes (weekly evaluations)
  
| Labs/seminar classes (weekly evaluations)
−
|align="center"| 30 <sup>1</sup>
 +
|align="center"| 30 <sup>0</sup>
 
|-
  
|-
 
| Interim performance assessment (class participation)
  
| Interim performance assessment (class participation)
Line 156: Line 70:
 
<sup>2</sup> Of which 35% for the written and 30% for the oral.
  
<sup>2</sup> Of which 35% for the written and 30% for the oral.
   
  +
Succi Giancarlo, [03.11.21 17:48]
 
Note: A student who has earned 70% of the grade before the oral exam (meaning 49% of the total grade), can apply for exemption to such oral exam, unless explicitly required by the instructor to take it, at full discretion of the instructor. In such case the grade final grade is computed as follows: all the grades below a total of 55% will award a C and all the one from 55% onward (up to 70%) will award a B. A student aiming at an A in the course has to do the oral exam.
  
Note: A student who has earned 70% of the grade before the oral exam (meaning 49% of the total grade), can apply for exemption to such oral exam, unless explicitly required by the instructor to take it, at full discretion of the instructor. In such case the grade final grade is computed as follows: all the grades below a total of 55% will award a C and all the one from 55% onward (up to 70%) will award a B. A student aiming at an A in the course has to do the oral exam.
   
Line 181: Line 96:
 
|align="center"| 25 <sup>2</sup>
  
|align="center"| 25 <sup>2</sup>
 
|}
  
|}
−  
−
<sup>1</sup> Of which 10 for online test done during the tutorial and 10 for homeworks related to labs.
  
−  
−
<sup>2</sup> Special cumulative oral.
  
−  
−  
−
'''In both case''' each component apart from homeworks will be assessed on a scale 0-10, where 6 is the minimum passing grade. In case of exceptional work a 10 cum laude will be assigned, with a numeric value from 11 to 13 at discretion of the instructor. The homeworks will be initially graded on a scale 0-2 weekly and then the overall grade will be assembled on a scale 0-10.<br />
  
−
The grading, though, is not a simple linear combination of the components above. In particular:
  
−  
−
* failing any part of the evaluation will trigger a failure in the entire course,
  
−
* the online test done during the tutorial, and the homeworks related to labs will be both averaged on the (n-4) best performances, where the 4 will be used to consider any kind of absence of the student, without requiring any additional documentation; if the student has legitimate reasons to be absent more than 4 times, then supporting document should be provided for all her/his absences,
  
−
* if there are not failing components, the final grade will be computed as a weighted average of the components above approximated at the highest second digit and then rounded to the closest integer.
  
−  
−
Note that the questions for the exam are taken from the textbooks with possible modifications of some parts of them.
  
−  
−
=== Retakes ===
  
−  
−
Retakes will be run as comprehensive oral exam, where the student will be assessed the acquired knowledge coming from the textbooks, the lectures, the tutorials, the labs, and the additional required reading material, as supplied by the instructor. During such comprehensive oral the student could be asked to solve exercises and to explain theoretical and practical aspects of the course.
  
   
 
=== Grades range ===
  
=== Grades range ===
Line 222: Line 119:
 
=== Resources and reference material ===
  
=== Resources and reference material ===
   
−
* '''Textbook:''' Andrew S. Tanenbaum and Herbert Bos. ''Modern Operating Systems'' (5th Edition), Pearson
 +
* '''Textbook:''' C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
  +
* '''Textbook:''' D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
−
* '''Reference:''' Andrew S. Tanenbaum and David J. Wetherall. Computer Networks (5th Edition), Pearson
  
−
* '''Reference:''' Brian W. Kernighan, Dennis M. Ritchie. The C Programming Language - 2nd Edition, Prentice Hall
  
−
* '''Reference:''' Maurice J.Bach. The design of the Unix Operating System, PRENTICE-HALL, INC., Englewood Cliffs, New Jersey 07632
  
   
 
== Course Sections ==
  
== Course Sections ==
   
−
The course is organized in 15 weeks with every weeks 2 academics hours of lectures, 2 academic hours of labs, and 2 academic hours of tutorials. The main sections of the course and approximate hour distribution between them is as follows:
 +
The main sections of the course and approximate hour distribution between them is
  +
as follows:
   
 
<div id="tab:OSCourseSections">
  
<div id="tab:OSCourseSections">
Line 240: Line 136:
 
|-
  
|-
 
|align="center"| 1
  
|align="center"| 1
−
| Revision of programming fundamentals for OS
 +
| Linear programming
−
|align="center"| 12
 +
|align="center"| 15
 
|-
  
|-
 
|align="center"| 2
  
|align="center"| 2
  +
| Nonlinear programming
−
| Processes and threads
  
−
|align="center"| 24
 +
|align="center"| 15
−
|-
  
−
|align="center"| 3
  
−
| Memory management
  
−
|align="center"| 24
  
−
|-
  
−
|align="center"| 4
  
−
| File system, I/O, and management of resources
  
−
|align="center"| 30
  
 
|}
  
|}
   
Line 260: Line 148:
 
=== Section 1 ===
  
=== Section 1 ===
   
−
==== Section title: Revision of programming fundamentals for OS ====
 +
==== Section title: Linear programming ====
   
   
 
==== Topics covered in this section ====
 
==== Topics covered in this section ====
   
  +
* simplex method to solve real linear programs
−
* Revision of the structure of a C program
  
  +
* cutting-plane and branch-and-bound methods to solve integer linear programs.
−
* Overall organization of the computation in C
  
  +
−
* Preprocessing
  
−
* Simulating function calls in preprocessing
  
−
* Analogies between macros and call by name
  
−
* Meaning of a variable in C
  
−
* Scope and extent of a variable
  
−
* Managing data structures with variable length
  
−
* Allocation and deallocation of memory
  
−
* Pointers and pointer arithmentics
  
−
* Pointers to functions
  
−
* Usage of pointers to function to simulate virtual functions
  
−
* Examples of usage of pointers to function in real life scenarios
  
−
* Pointers to functions to perform map and reduce
  
   
 
==== What forms of evaluation were used to test students’ performance in this section? ====
 
==== What forms of evaluation were used to test students’ performance in this section? ====
Line 289: Line 166:
 
|-
  
|-
 
| Development of individual parts of software product code
  
| Development of individual parts of software product code
−
|align="center"| 1
 +
|align="center"| 0
 
|-
  
|-
 
| Homework and group projects
  
| Homework and group projects
Line 295: Line 172:
 
|-
  
|-
 
| Midterm evaluation
  
| Midterm evaluation
−
|align="center"| 0
 +
|align="center"| 1
 
|-
  
|-
 
| Testing (written or computer based)
  
| Testing (written or computer based)
Line 307: Line 184:
 
|-
  
|-
 
| Oral polls
  
| Oral polls
−
|align="center"| 1
 +
|align="center"| 0
 
|-
  
|-
 
| Discussions
  
| Discussions
−
|align="center"| 1
 +
|align="center"| 0
 
|}
  
|}
   
Line 317: Line 194:
 
==== Typical questions for ongoing performance evaluation within this section ====
 
==== Typical questions for ongoing performance evaluation within this section ====
   
  +
# How a convex set and a convex function are defined?
−
# Explain the difference between an include file and a library.
  
  +
# What is the difference between polyhedron and polytope?
−
# Is a parameter of a macro a “real” parameter?
  
  +
# Why does always a linear program include constraints?
−
# Discuss the importance of the conditional compilation.
  
−
# What happens when a function returning a pointer returns the address of a local variable?
  
−
# Detail the meaning of the keyword static and external for supporting information hiding.
  
−
# Describe how the use of virtual functions can make the code more flexible.
  
−  
−
==== Typical questions for seminar classes (labs) within this section ====
 
−  
−
# Given a source .c file including a .h header file, show the results of preprossing in terms of the generated c file.
  
−
# Write a macro and a function in C for the same purpose and discuss pros and cons of both approaches.
  
−
# Show how you can write a generic swap function as a macro.
  
−
# Write the code allocating dynamic memory for a 2 dimensional array and initializing it.
  
−
# Provide an example of how with pointers it is possible in the called function to alter values of variable located in the calling function.
  
−
# Using function pointers, write a sorting function having the sorting rule as a parameter of such function.
  
   
 
==== Test questions for final assessment in this section ====
 
==== Test questions for final assessment in this section ====
   
  +
# Why does the simplex method require to be initialized with a correct basic feasible solution?
−
# Discuss the difference in the compiled code when using function and when using macros instead.
  
  +
# How one can test absence of solutions to a linear program?
−
# Provide examples of functions that cannot be transformed into macros, also discussing the motivation for such impossibility.
  
  +
# How one can test unbounded solutions to a linear program?
−
# Describe the rules for scope and extent for local variables, static variables (in all cases), and pointers, supplying also code examples of them.
  
  +
# How can the computational complexity of an optimization algorithm can be defined?
−
# Detail the structure of the address space of a process when using a three dimensional array allocated as a local variable of a function and when such array is allocated dynamically, also describe the types of the variables in use and how the compiler checks them.
  
  +
−
# Outline the assembly code for a function calling another function passed as a parameter of it.
  
   
 
=== Section 2 ===
  
=== Section 2 ===
   
−
==== Section title: Processes and Threads ====
+
==== Section title: Nonlinear programming ====
   
   
 
==== Topics covered in this section ====
 
==== Topics covered in this section ====
   
  +
* methods for unconstrained optimization
−
* Process models
  
  +
* linear and nonlinear least-squares problems
−
* Process creation and termination
  
  +
* methods for constrained optimization
−
* Process hierarchies
  
  +
−
* Process states
  
−
* Implementation of processes
  
−
* Threads
  
−
* Interprocess communication
  
−
* Races
  
−
* Critical regions, busy waiting, sleep and wakeup
  
−
* Semaphores
  
−
* Monitors
  
−
* Principles of scheduling
  
−
* Categories of scheduling algorithms
  
−
* Most common approaches for scheduling in interactive systems
  
   
 
==== What forms of evaluation were used to test students’ performance in this section? ====
 
==== What forms of evaluation were used to test students’ performance in this section? ====
Line 372: Line 227:
 
|-
  
|-
 
| Development of individual parts of software product code
  
| Development of individual parts of software product code
−
|align="center"| 1
 +
|align="center"| 0
 
|-
  
|-
 
| Homework and group projects
  
| Homework and group projects
Line 378: Line 233:
 
|-
  
|-
 
| Midterm evaluation
  
| Midterm evaluation
−
|align="center"| 0
 +
|align="center"| 1
 
|-
  
|-
 
| Testing (written or computer based)
  
| Testing (written or computer based)
Line 390: Line 245:
 
|-
  
|-
 
| Oral polls
  
| Oral polls
−
|align="center"| 1
  
−
|-
  
−
| Discussions
  
−
|align="center"| 1
  
−
|}
  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
 
−  
−
# Outline the typical life of a process from creation to termination
  
−
# Present the different possible models of waiting
  
−
# Define the concept of a semaphore and how it can be implemented
  
−
# Explain the concept of a monitor from a programming standpoint and how it relates to modern programming paradigms.
  
−
# Discuss advantages and disadvantages of the different scheduling algorithms
  
−  
−
==== Typical questions for seminar classes (labs) within this section ====
 
−  
−
# Write a shell script that produces a file of sequential numbers by reading the last number in the file, adding 1 to it, and then appending it to the file. Run one instance of the script in the background and one in the foreground, each accessing the same file. Answer the following questions: (a) How long does it take before a race condition manifests itself? (b) What is the critical region? (c) How you can modify the script to prevent the race
  
−
# Write a producer-consumer problem that uses threads and shares a common buffer. However, do not use semaphores or any other synchronization primitives to guard the shared data structures. Just let each thread access them when it wants to. Use sleep and wakeup to handle the full and empty conditions. See how long it takes for a fatal race condition to occur. For example, you might have the producer print a number once in a while. Do not print more than one number every minute because the I/O could affect the race conditions.
  
−
# Write a program that creates a pipe. Have two strings – one should contain some text, the other one should be empty. Transfer a text from the first string to another one using the pipe you created. Show the result.
  
−
# Write a C program that forks a child process, waits for 10 seconds and then sends a SIGTERM signal to the child. The child process should run an infinite loop and print “I’m alive” every second
  
−
# Write the solution for the produced-consumer problem using monitors.
  
−  
−
==== Test questions for final assessment in this section ====
 
−  
−
# ''From the textbook:'' Multiple jobs can run in parallel and finish faster than if they had run sequentially. Suppose that two jobs, each needing 20 minutes of CPU time, start simultaneously. How long will the last one take to complete if they run sequentially? How long if they run in parallel? Assume 50% I/O wait.
  
−
# ''From the textbook:'' The readers and writers problem can be formulated in several ways with regard to which category of processes can be started when. Carefully describe three different variations of the problem, each one favoring (or not favoring) some category of processes. For each variation, specify what happens when a reader or a writer becomes ready to access the database, and what happens when a process is finished?
  
−
# ''From the textbook:'' Consider a system in which threads are implemented entirely in user space, with the run-time system getting a clock interrupt once a second. Suppose that a clock interrupt occurs while some thread is executing in the run-time system. What problem might occur? Can you suggest a way to solve it?
  
−
# ''From the textbook:'' In this problem you are to compare reading a file using a single-threaded file server and a multithreaded server. It takes 12 msec to get a request for work, dispatch it, and do the rest of the necessary processing, assuming that the data needed are in the block cache. If a disk operation is needed, as is the case one-third of the time, an additional 75 msec is required, during which time the thread sleeps. How many requests/sec can the server handle if it is single threaded? If it is multithreaded?
  
−
# ''From the textbook:'' There are five batch jobs: A through E, they arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. Consider the following scheduling algorithms: '''(a)''' Round robin, '''(b)''' Priority scheduling, '''(c)''' First-come, first-served (run in order 10, 6, 2, 4, 8), '''(d)''' Shortest job first. For each mentioned scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead. For (a), assume that the system is multi-programmed, and that each job gets its fair share of the CPU. For (b) through (d), assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
  
−  
−
=== Section 3 ===
  
−  
−
==== Section title: Memory management ====
 
−  
−
==== Topics covered in this section ====
 
−  
−
* Address space
  
−
* Memory abstraction
  
−
* Based and limit registers
  
−
* Swapping
  
−
* Virtual memory
  
−
* Paging
  
−
* Implementation of paging
  
−
* Page replacement algorithms
  
−
* Page faults
  
−
* Segmentation
  
−
* Segmentation with paging
  
−  
−
==== What forms of evaluation were used to test students’ performance in this section? ====
 
−  
−
<div id="tab:OSSectionEval3">
  
−  
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|''' '''
  
−
! '''Yes/No'''
  
−
|-
  
−
| Development of individual parts of software product code
  
−
|align="center"| 1
  
−
|-
  
−
| Homework and group projects
  
−
|align="center"| 1
  
−
|-
  
−
| Midterm evaluation
  
 
|align="center"| 0
  
|align="center"| 0
−
|-
  
−
| Testing (written or computer based)
  
−
|align="center"| 1
  
−
|-
  
−
| Reports
  
−
|align="center"| 0
  
−
|-
  
−
| Essays
  
−
|align="center"| 0
  
−
|-
  
−
| Oral polls
  
−
|align="center"| 1
  
 
|-
  
|-
 
| Discussions
  
| Discussions
−
|align="center"| 1
  
−
|}
  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
 
−  
−
# What are the base and limit registers and what are the problems related to their usage?
  
−
# Can you have swapping in absence of paging? And paging in absence of swapping?
  
−
# What mechanisms and algorithms are available to handle effectively paging?
  
−
# Details advantages and disadvantages of the different page replacement algorithms.
  
−
# Describe the difference between paging and segmenting.
  
−
# Is it possible to combine segmenting and paging? If so, how?
  
−  
−
==== Typical questions for seminar classes (labs) within this section ====
 
−  
−
# Run ‘free -t -h‘ in a Linux shell or ‘vmstat‘ in a macOS one. Discuss the output.
  
−
# Write a C program that runs for 10 seconds. Every second it should: (a) allocate 10 MB of memory – fill it with zeros, (b) sleep for 1 second. Then, compile and run the program in the background (./ex2 &amp;) and run ‘vmstat 1’ at the same time. Observe what happens to the memory. Pay attention to si and so fields. ''Hint:'' use memset(ptr, value, size) to fill the allocated memory.
  
−
# Write a program that simulates a paging system using the ageing algorithm. The number of page frames is a parameter. The sequence of page references should be read from a file. For a given input file, your program should print Hit/Miss ratio.
  
−
# Try to construct a sequence of references that will result in increased or decreased Hit/Miss ratio.
  
−
# ''From the textbook:'' A machine has 16-bit virtual addresses. Pages are 8 KB. How many entries are needed for a single-level linear page table? Explain your computations.
  
−  
−
==== Test questions for final assessment in this section ====
 
−  
−
# ''From the textbook:'' A computer provides each process with 65,536 bytes of address space divided into pages of 4096 bytes each. A particular program has a text size of 32,768 bytes, a data size of 16,386 bytes, and a stack size of 15,870 bytes. Will this program fit in the machine’s address space? Suppose that instead of 4096 bytes, the page size were 512 bytes, would it then fit? Each page must contain either text, data, or stack, not a mixture of two or three of them.
  
−
# ''From the textbook:'' You are given the following data about a virtual memory system: '''1.''' The TLB can hold 1024 entries and can be accessed in 1 clock cycle (1 nsec). '''2.''' A page table entry can be found in 100 clock cycles or 100 nsec. '''3.'''The average page replacement time is 6 msec. If page references are handled by the TLB 99% of the time, and only 0.01% lead to a page fault, what is the effective address-translation time?
  
−
# ''From the textbook:'' A small computer on a smart card has four page frames. At the first clock tick, the R bits are 0111 (page 0 is 0, the rest are 1). At subsequent clock ticks, the values are 1011, 1010, 1101, 0010, 1010, 1100, and 0001. If the aging algorithm is used with an 8-bit counter, give the values of the four counters after the last tick.
  
−
# ''From the textbook:'' A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page table field, an 11-bit second-level page table field, and an offset. How large are the pages and how many are there in the address space?
  
−
# ''From the textbook:'' A computer has 32-bit virtual addresses and 4-KB pages. The program and data together fit in the lowest page (0–4095) The stack fits in the highest page. How many entries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with 10 bits in each part?
  
−  
−
=== Section 4 ===
  
−  
−
==== Section title: File system, I/O, and management of resources ====
 
−  
−  
−
==== Topics covered in this section ====
 
−  
−
* File system
  
−
* Files and files types, attributes, and operations
  
−
* Paths
  
−
* File system layout
  
−
* Shared files
  
−
* File system backups
  
−
* FIle system performances
  
−
* General structure of I/O
  
−
* Block devices and character devices
  
−
* Device drivers
  
−
* Memory mapped I/O and Direct Memory Access
  
−
* Interrupts
  
−
* Programmed I/O
  
−
* Deadlocks
  
−
* Conditions for deadlocks
  
−
* Strategies to deal with dealocks
  
−  
−
==== What forms of evaluation were used to test students’ performance in this section? ====
 
−  
−
<div id="tab:OSSectionEval4">
  
−  
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|''' '''
  
−
! '''Yes/No'''
  
−
|-
  
−
| Development of individual parts of software product code
  
−
|align="center"| 1
  
−
|-
  
−
| Homework and group projects
  
−
|align="center"| 1
  
−
|-
  
−
| Midterm evaluation
  
 
|align="center"| 0
  
|align="center"| 0
−
|-
  
−
| Testing (written or computer based)
  
−
|align="center"| 1
  
−
|-
  
−
| Reports
  
−
|align="center"| 0
  
−
|-
  
−
| Essays
  
−
|align="center"| 0
  
−
|-
  
−
| Oral polls
  
−
|align="center"| 1
  
−
|-
  
−
| Discussions
  
−
|align="center"| 1
  
 
|}
  
|}
   
Line 561: Line 255:
 
==== Typical questions for ongoing performance evaluation within this section ====
 
==== Typical questions for ongoing performance evaluation within this section ====
   
  +
# Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem?
−
# What is the overall structure of a file system
  
  +
# What is the goal of a descent algorithm?
−
# How are files and directories organized on a disk and what are the roles of i-nodes, when they are used
  
  +
# What does it mean to fit some experimental data points
−
# What are the key differences between block and character devices.
  
−
# How does DMA speeds up the computations?
  
−
# List the major classes of strategies to handle deadlock.
  
−  
−
==== Typical questions for seminar classes (labs) within this section ====
 
−  
−
# Create tmp directory with two empty files (file1, file2). Then, create one hard link named link1 to file1. Write a program that scans tmp directory, locates all i-nodes with a hard link count of two or more and for each such file it should display together all file names that point to the file.
  
−
# Implement a simulated file system that will be fully contained in a single regular file stored on the disk. This disk file will contain directories, i-nodes, free- block information, file data blocks, etc. Choose appropriate algorithms for maintaining free-block information and for allocating data blocks (contiguous, indexed, linked). Your program will accept system commands from the user to create/delete directories, create/delete/open files, read/write from/to a selected file, and to list directory contents.
  
−
# Create a file ex1.txt with a random string in it. Write a C program (ex1.c) that changes the string in ex1.txt to “This is a nice day” by using mmap(). Hints: '''(a)''' open the file in O_RDWR mode, '''(b)''' use stat() or fstat() to get the size of the file.
  
−
# Write a C program (ex2.c) using line buffer. Write your code according to the instructions: '''(a)''' each of the 5 characters of “Hello” string should be put in separate printf(), '''(b)''' add a 1 sec sleep after every printf(). The output should be a 5 sec wait and then “Hello” printed instantaneously.
  
−
# The tee command reads its standard input until end-of- file, writing a copy of the input to standard output and to the files named in its command-line arguments. Implement tee using I/O system calls. By default, tee overwrites any existing file with the given name. Implement the -a command-line option (tee -a file), which causes tee to append text to the end of a file if it already exists.
  
−
# Write a C program for deadlock detection algorithm reading the resources available form a file (input.txt). For testing purposes consider 5 processes and 3 type of resources. However, your program must be able to process as many processes and resource types, as needed (check next slide for input file structure description). The output of your program should either say that no deadlock is detected or print out the numbers of processes that are deadlocked.
  
   
−
==== Test questions for final assessment in this section ====
+
==== Test questions for final assessment in this section ====
   
  +
# How is it possible to compute the Lagrange multiplier of a constrained optimization problem?
−
# ''From the textbook:'' Two computer science students, Carolyn and Elinor, are having a discussion about i-nodes. Carolyn maintains that memories have gotten so large and so cheap that when a file is opened, it is simpler and faster just to fetch a new copy of the i-node into the i-node table, rather than search the entire table to see if it is already there. Elinor disagrees. Who is right? Why?
  
  +
# Which are the convergence conditions of the steepest descent method?
−
# ''From the textbook:'' A typical printed page of text contains 50 lines of 80 characters each. Imagine that a certain printer can print 6 pages per minute and that the time to write a character to the printer’s output register is so short it can be ignored. Does it make sense to run this printer using interrupt-driven I/O if each character printed requires an interrupt that takes 50 <math display="inline">\mu</math>sec all-in to service?
  
  +
# Which are the convergence conditions of the Newton’s method?
−
# ''From the textbook:'' Consider a disk that has 10 data blocks starting from block 14 through 23. Let there be 2 files on the disk: f1 and f2. The directory structure lists that the first data blocks of f1 and f2 are respectively 22 and 16. The FAT table is as follows: (14,18), (15,17), (16,23), (17,21), (18,20), (19,15), (20,-1), (21,-1), (22,19), (23,14), where (x,y) indicates that the value stored in table entry x points to data block y. What are the data blocks allotted to f1 and f2?
  
  +
# How can one “penalize” a constraint?
−
# ''From the textbook:'' Explain how hard links and soft links differ with respective to i-node allocations.
  
−
# ''From the textbook:'' When a user program makes a system call to read or write a disk file, it provides an indication of which file it wants, a pointer to the data buffer, and the count. Control is then transferred to the operating system, which calls the appropriate driver. Suppose that the driver starts the disk and terminates until an interrupt occurs. In the case of reading from the disk, obviously the caller will have to be blocked (because there are no data for it). What about the case of writing to the disk? Need the caller be blocked awaiting completion of the disk transfer?
  
−
# ''From the textbook:'' The banker’s algorithm is being run in a system with m resource classes and n processes. In the limit of large m and n, the number of operations that must be performed to check a state for safety is proportional to m<math display="inline">^a</math>n<math display="inline">^b</math> . What are the values of a and b ?
  

Revision as of 20:11, 3 November 2021

Optimization

  • Course name: Optimization
  • Course number: R-01

Course characteristics

Key concepts of the class

  • Optimization of a cost function
  • Algorithms to find solution of linear and nonlinear optimization problems

What is the purpose of this course?

The main purpose of this course to make the student aware of basic notions of mathematical programming and of its importance in the area of engineering.

Course Objectives Based on Bloom’s Taxonomy

What should a student remember at the end of the course?

By the end of the course, the students should be able to recognize and define:

  • explain the goal of some optimization problems
  • remind the importance of converge analysis for optimization algorithms
  • draft solution codes in Python/Matlab.

What should a student be able to understand at the end of the course?

By the end of the course, the students should be able to describe and explain (with examples):

  • formulate a simple optimization problem
  • select the appropriate solution algorithm
  • find the solution.

What should a student be able to apply at the end of the course?

By the end of the course, the students should be able to apply:

  • the simplex method
  • algorithms to solve nonlinear optimization problems.

Course evaluation

The course has two major forms of evaluations:

  • a standard evaluation,
  • for very motivated students, an alternative form of evaluation.

The standard evaluation follows.

Course grade breakdown
Component Points
Labs/seminar classes (weekly evaluations) 30 0
Interim performance assessment (class participation) 5
Exams 65 2

1 Of which 15 for online test done during the tutorial, 15 for homeworks related to labs.

2 Of which 35% for the written and 30% for the oral.

Succi Giancarlo, [03.11.21 17:48] Note: A student who has earned 70% of the grade before the oral exam (meaning 49% of the total grade), can apply for exemption to such oral exam, unless explicitly required by the instructor to take it, at full discretion of the instructor. In such case the grade final grade is computed as follows: all the grades below a total of 55% will award a C and all the one from 55% onward (up to 70%) will award a B. A student aiming at an A in the course has to do the oral exam.


The alternative evaluation follows.

The alternative form of evaluation assumes attendance to all lecture and always a grade above 9/10 or equivalent. Students interested to opt for this approach need to inform Xavier Vasquez about their choice no later than during the third Tutorial (1st September). If during the semester a student fails to satisfy the criteria for taking the alternative form of evaluation, s/he is automatically reverted to the standard evaluation.

Course grade breakdown
Component Points
Labs/seminar classes (weekly evaluations) 20 1
Interim performance assessment (class participation) 5
Solutions to questions of Bach directly in the text 50
Exams 25 2

Grades range

Course grading range
A. Excellent 96-100
B. Good 66-95
C. Satisfactory 56-65
D. Poor 0-55

Resources and reference material

  • Textbook: C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
  • Textbook: D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.

Course Sections

The main sections of the course and approximate hour distribution between them is as follows:

Course Sections
Section Section Title Teaching Hours
1 Linear programming 15
2 Nonlinear programming 15


Section 1

Section title: Linear programming

Topics covered in this section

  • simplex method to solve real linear programs
  • cutting-plane and branch-and-bound methods to solve integer linear programs.


What forms of evaluation were used to test students’ performance in this section?

Yes/No
Development of individual parts of software product code 0
Homework and group projects 1
Midterm evaluation 1
Testing (written or computer based) 1
Reports 0
Essays 0
Oral polls 0
Discussions 0


Typical questions for ongoing performance evaluation within this section

  1. How a convex set and a convex function are defined?
  2. What is the difference between polyhedron and polytope?
  3. Why does always a linear program include constraints?

Test questions for final assessment in this section

  1. Why does the simplex method require to be initialized with a correct basic feasible solution?
  2. How one can test absence of solutions to a linear program?
  3. How one can test unbounded solutions to a linear program?
  4. How can the computational complexity of an optimization algorithm can be defined?


Section 2

Section title: Nonlinear programming

Topics covered in this section

  • methods for unconstrained optimization
  • linear and nonlinear least-squares problems
  • methods for constrained optimization


What forms of evaluation were used to test students’ performance in this section?

Yes/No
Development of individual parts of software product code 0
Homework and group projects 1
Midterm evaluation 1
Testing (written or computer based) 1
Reports 0
Essays 0
Oral polls 0
Discussions 0


Typical questions for ongoing performance evaluation within this section

  1. Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem?
  2. What is the goal of a descent algorithm?
  3. What does it mean to fit some experimental data points

Test questions for final assessment in this section

  1. How is it possible to compute the Lagrange multiplier of a constrained optimization problem?
  2. Which are the convergence conditions of the steepest descent method?
  3. Which are the convergence conditions of the Newton’s method?
  4. How can one “penalize” a constraint?
Retrieved from "https://eduwiki.innopolis.university/index.php?title=MSc:_Optimization&oldid=1113"