Difference between revisions of "MSc: Optimization"

From IU
Jump to navigation Jump to search
 
(20 intermediate revisions by 5 users not shown)
Line 1: Line 1:
  +
 
= Optimization =
  
= Optimization =
  +
* '''Course name''': Optimization
  +
* '''Code discipline''': R-01
  +
* '''Subject area''':
   
  +
== Short Description ==
−
* <span>'''Course name:'''</span> Optimization
  
  +
This course covers the following concepts: Optimization of a cost function; Algorithms to find solution of linear and nonlinear optimization problems.
−
* <span>'''Course number:'''</span> R-01
  
−  
−
== Course Characteristics ==
  
−  
−
* <span>'''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 ==
  
== Prerequisites ==
   
  +
=== Prerequisite subjects ===
−
Familiarity with multivariate calculus, elementary real analysis, and linear algebra.
  
   
−
* Multivariate calculus
  
−
* Linear Algebra
  
   
−
== Course outline ==
 +
=== Prerequisite topics ===
   
−
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 ==
 +
== Course Topics ==
  +
{| class="wikitable"
−  
  +
|+ Course Sections and Topics
−
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 ==
  
−  
−
=== Key concepts of the class ===
  
−  
−
* Structure of an operating system
  
−
* Specific mechanisms, policies, and algorithms used to implement the different parts of an operating system
  
−  
−
=== What is the purpose of this course? ===
  
−  
−
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 ===
  
−  
−
==== 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:
  
−  
−
* fundamental components of an Operating Systems,
  
−
* organization of primary memory and the associated concept of virtual memory, with techniques based on paging and segmenting,
  
−
* 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? ====
  
−  
−
By the end of the course, the students should be able to describe and explain (with examples):
  
−  
−
* strategies and algorithms for allocating processor(s) time to processes,
  
−
* strategies and algorithms for allocating primary memory to processes,
  
−
* 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? ====
  
−  
−
By the end of the course, the students should be able to apply:
  
−  
−
* strategies for programming at the Operating System level,
  
−
* 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 ===
  
−  
−
The course has two major forms of evaluations:
  
−  
−
* a standard evaluation,
  
−
* for very motivated students, an alternative form of evaluation.
  
−  
−
The '''standard evaluation''' follows.
  
−  
−
<div id="tab:OSCourseGrading">
  
−  
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|+ '''Course grade breakdown'''
  
−
!align="center"| '''Component'''
  
−
! '''Points'''
  
 
|-
  
|-
  +
! Section !! Topics within the section
−
| Labs/seminar classes (weekly evaluations)
  
−
|align="center"| 30 <sup>1</sup>
  
 
|-
  
|-
  +
| Linear programming ||
−
| Interim performance assessment (class participation)
  
  +
# simplex method to solve real linear programs
−
|align="center"| 5
  
  +
# cutting-plane and branch-and-bound methods to solve integer linear programs.
 
|-
  
|-
  +
| Nonlinear programming ||
−
| Exams
  
  +
# methods for unconstrained optimization
−
|align="center"| 65 <sup>2</sup>
  
  +
# linear and nonlinear least-squares problems
−
|}
  
  +
# methods for constrained optimization
  +
|}
  +
== Intended Learning Outcomes (ILOs) ==
   
  +
=== What is the main purpose of this course? ===
−
<sup>1</sup> Of which 15 for online test done during the tutorial, 15 for homeworks related to labs.
  
  +
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.
   
  +
=== ILOs defined at three levels ===
−
<sup>2</sup> Of which 35% for the written and 30% for the oral.
  
   
  +
==== Level 1: What concepts should a student know/remember/explain? ====
−
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.
  
  +
By the end of the course, the students should be able to ...
  +
* explain the goal of an optimization problem
  +
* remind the importance of converge analysis for optimization algorithms
  +
* draft solution codes in Python/Matlab.
   
  +
==== Level 2: What basic practical skills should a student be able to perform? ====
  +
By the end of the course, the students should be able to ...
  +
* formulate a simple optimization problem
  +
* select the appropriate solution algorithm
  +
* find the solution.
   
  +
==== Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios? ====
−
</div>
  
  +
By the end of the course, the students should be able to ...
−
The '''alternative evaluation''' follows.
  
  +
* the simplex method
  +
* algorithms to solve nonlinear optimization problems.
  +
== Grading ==
   
  +
=== Course grading range ===
−
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.
  
  +
{| class="wikitable"
−  
  +
|+
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|+ '''Course grade breakdown'''
  
−
!align="center"| '''Component'''
  
−
! '''Points'''
  
 
|-
  
|-
  +
! Grade !! Range !! Description of performance
−
| Labs/seminar classes (weekly evaluations)
  
−
|align="center"| 20 <sup>1</sup>
  
 
|-
  
|-
  +
| A. Excellent || 86-100 || -
−
| Interim performance assessment (class participation)
  
−
|align="center"| 5
  
 
|-
  
|-
  +
| B. Good || 71-85 || -
−
| Solutions to questions of Bach directly in the text
  
−
|align="center"| 50
  
 
|-
  
|-
  +
| C. Satisfactory || 56-70 || -
−
| Exams
  
−
|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 ===
  
−  
−
<div id="tab:OSCourseGradingRange">
  
−  
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|+ Course grading range
  
 
|-
  
|-
  +
| D. Poor || 0-55 || -
−
| A. Excellent
  
−
|align="center"| 96-100
  
−
|-
  
−
| B. Good
  
−
|align="center"| 66-95
  
−
|-
  
−
| C. Satisfactory
  
−
|align="center"| 56-65
  
−
|-
  
−
| D. Poor
  
−
|align="center"| 0-55
  
 
|}
  
|}
   
−
=== Resources and reference material ===
 +
=== Course activities and grading breakdown ===
  +
{| class="wikitable"
−  
  +
|+
−
* '''Textbook:''' Andrew S. Tanenbaum and Herbert Bos. ''Modern Operating Systems'' (5th Edition), Pearson
  
−
* '''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 ==
  
−  
−
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:
  
−  
−
<div id="tab:OSCourseSections">
  
−  
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|+ Course Sections
  
−
!align="center"| '''Section'''
  
−
! '''Section Title'''
  
−
!align="center"| '''Teaching Hours'''
  
 
|-
  
|-
  +
! Activity Type !! Percentage of the overall course grade
−
|align="center"| 1
  
−
| Revision of programming fundamentals for OS
  
−
|align="center"| 12
  
 
|-
  
|-
  +
| Labs/seminar classes (weekly evaluations) || 0
−
|align="center"| 2
  
−
| Processes and threads
  
−
|align="center"| 24
  
 
|-
  
|-
  +
| Interim performance assessment (class participation) || 100/0
−
|align="center"| 3
  
−
| Memory management
  
−
|align="center"| 24
  
 
|-
  
|-
  +
| Exams || 0/100
−
|align="center"| 4
  
−
| File system, I/O, and management of resources
  
−
|align="center"| 30
  
 
|}
  
|}
   
  +
=== Recommendations for students on how to succeed in the course ===
   
−
</div>
  
−
=== Section 1 ===
  
   
  +
== Resources, literature and reference materials ==
−
==== Section title: Revision of programming fundamentals for OS ====
  
   
  +
=== Open access resources ===
  +
* Textbook: C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
  +
* Textbook: D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
   
−
==== Topics covered in this section ====
+
=== Closed access resources ===
   
−
* Revision of the structure of a C program
  
−
* 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
  
   
  +
=== Software and tools used within the course ===
−
==== What forms of evaluation were used to test students’ performance in this section? ====
 
  +
  +
= Teaching Methodology: Methods, techniques, & activities =
   
  +
== Activities and Teaching Methods ==
−
<div id="tab:OSSectionEval1">
  
  +
{| class="wikitable"
−  
  +
|+ Activities within each section
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
−
|''' '''
  
−
! '''Yes/No'''
  
 
|-
  
|-
  +
! Learning Activities !! Section 1 !! Section 2
−
| Development of individual parts of software product code
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Midterm evaluation || 1 || 1
−
| Homework and group projects
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Testing (written or computer based) || 1 || 1
−
| Midterm evaluation
  
  +
|}
−
|align="center"| 0
  
  +
== Formative Assessment and Course Activities ==
−
|-
  
−
| 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
  
−
|}
  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
 
−  
−
# Explain the difference between an include file and a library.
  
−
# Is a parameter of a macro a “real” parameter?
  
−
# 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 ====
 
−  
−
# Discuss the difference in the compiled code when using function and when using macros instead.
  
−
# Provide examples of functions that cannot be transformed into macros, also discussing the motivation for such impossibility.
  
−
# Describe the rules for scope and extent for local variables, static variables (in all cases), and pointers, supplying also code examples of them.
  
−
# 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 title: Processes and Threads ====
 
−  
−  
−
==== Topics covered in this section ====
 
−  
−
* Process models
  
−
* Process creation and termination
  
−
* 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? ====
 
   
  +
=== Ongoing performance assessment ===
−
<div id="tab:OSSectionEval2">
  
   
  +
==== Section 1 ====
−
{| style="border-spacing: 2px; border: 1px solid darkgray;"
  
  +
{| class="wikitable"
−
|''' '''
  
  +
|+
−
! '''Yes/No'''
  
 
|-
  
|-
  +
! Activity Type !! Content !! Is Graded?
−
| Development of individual parts of software product code
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Question || How a convex set and a convex function are defined? || 1
−
| Homework and group projects
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Question || What is the difference between polyhedron and polytope? || 1
−
| Midterm evaluation
  
−
|align="center"| 0
  
 
|-
  
|-
  +
| Question || Why does always a linear program include constraints? || 1
−
| Testing (written or computer based)
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}+c_{4}x_{4}}</math> <br><math>{\displaystyle {\text{subject to }}x_{1}+x_{2}+x_{3}+x_{4}=2}</math> <br><math>{\displaystyle 2x_{1}+3x_{3}+4x_{4}=2}</math> <br><math>{\displaystyle x_{1},x_{2},x_{3},x_{4}\geqslant 0}</math> <br>Solve it using simplex method. || 0
−
| Reports
  
−
|align="center"| 0
  
 
|-
  
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}x_{1}+x_{2}}</math> <br><math>{\displaystyle {\text{subject to }}-5x_{1}+4x_{2}\leq 0}</math> <br><math>{\displaystyle 6x_{1}+2x_{2}\ \leq 17}</math> <br><math>{\displaystyle x_{1},\ x_{2}\geq 0}</math> <br>Solve it using cutting-plane and branch-and-bound methods. || 0
−
| Essays
  
  +
|}
−
|align="center"| 0
  
  +
==== Section 2 ====
  +
{| class="wikitable"
  +
|+
 
|-
  
|-
  +
! Activity Type !! Content !! Is Graded?
−
| Oral polls
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Question || Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem? || 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'''
  
 
|-
  
|-
  +
| Question || What is the goal of a descent algorithm? || 1
−
| Development of individual parts of software product code
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Question || What does it mean to fit some experimental data points || 1
−
| Homework and group projects
  
−
|align="center"| 1
  
 
|-
  
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}{\frac {1}{2}}\left(x_{1}^{1}+x_{2}^{2}\right)}</math> <br>Solve it using the suitable method. || 0
−
| Midterm evaluation
  
−
|align="center"| 0
  
 
|-
  
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}-\left(x_{1}-2\right)^{2}}</math> <br><math>{\displaystyle {\text{subject to }}\ x_{1}+x_{2}^{2}=1}</math> <br><math>{\displaystyle -1\leq x_{2}\leq 1}</math> <br>Solve it using the suitable method. || 0
−
| Testing (written or computer based)
  
  +
|}
−
|align="center"| 1
  
  +
=== Final assessment ===
−
|-
  
  +
'''Section 1'''
−
| Reports
  
  +
# Why does the simplex method require to be initialized with a correct basic feasible solution?
−
|align="center"| 0
  
  +
# How one can test absence of solutions to a linear program?
−
|-
  
  +
# How one can test unbounded solutions to a linear program?
−
| Essays
  
  +
# How can the computational complexity of an optimization algorithm can be defined?
−
|align="center"| 0
  
  +
'''Section 2'''
−
|-
  
  +
# How is it possible to compute the Lagrange multiplier of a constrained optimization problem?
−
| Oral polls
  
  +
# Which are the convergence conditions of the steepest descent method?
−
|align="center"| 1
  
  +
# Which are the convergence conditions of the Newton’s method?
−
|-
  
  +
# How can one “penalize” a constraint?
−
| 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
  
−
|-
  
−
| 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
  
−
|}
  
−  
−  
−
</div>
  
−
==== Typical questions for ongoing performance evaluation within this section ====
 
−  
−
# What is the overall structure of a file system
  
−
# How are files and directories organized on a disk and what are the roles of i-nodes, when they are used
  
−
# 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.
  
   
  +
=== The retake exam ===
−
==== Test questions for final assessment in this section ====
 
  +
'''Section 1'''
  +
# Consider the problem:
  +
<math>{\displaystyle {\text{minimize }}x_{1}+x_{2}}</math>
  +
<math>{\displaystyle {\text{subject to }}x_{1}+{2x}_{2}+2x_{3}\leq 20}</math>
  +
<math>{\displaystyle 2x_{1}+x_{2}+2x_{3}\leq 20}</math>
  +
<math>{\displaystyle 2x_{1}+2x_{2}+x_{3}\leq 20}</math>
  +
<math>{\displaystyle x_{1},\ x_{2},\ x_{3}\geq 0}</math>
  +
Solve it using simplex method.
  +
# Consider the problem:
  +
<math>{\displaystyle {\text{maximize }}15x_{1}+{12x}_{2}+4x_{3}+2x_{4}}</math>
  +
<math>{\displaystyle {\text{subject to }}8x_{1}+5x_{2}+3x_{3}+2x_{4}\leq 10}</math>
  +
<math>{\displaystyle x_{i}\in \{0,1\}}</math>
  +
Solve it using cutting-plane and branch-and-bound methods.
   
  +
'''Section 2'''
−
# ''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?
  
  +
# Consider the problem:
−
# ''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?
  
  +
<math>{\displaystyle {\text{minimize }}100\left(x_{2}-x_{1}^{2}\right)^{2}+\left(1-x_{1}\right)^{2}}</math>
−
# ''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?
  
  +
<math>{\displaystyle {\text{subject to }}x_{1},\ x_{2}\geq 0}</math>
−
# ''From the textbook:'' Explain how hard links and soft links differ with respective to i-node allocations.
  
  +
Solve it using the suitable method.
−
# ''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 ?
  

Latest revision as of 14:09, 10 November 2022

Optimization

  • Course name: Optimization
  • Code discipline: R-01
  • Subject area:

Short Description

This course covers the following concepts: Optimization of a cost function; Algorithms to find solution of linear and nonlinear optimization problems.

Prerequisites

Prerequisite subjects

Prerequisite topics

Course Topics

Course Sections and Topics
Section Topics within the section
Linear programming
  1. simplex method to solve real linear programs
  2. cutting-plane and branch-and-bound methods to solve integer linear programs.
Nonlinear programming
  1. methods for unconstrained optimization
  2. linear and nonlinear least-squares problems
  3. methods for constrained optimization

Intended Learning Outcomes (ILOs)

What is the main 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.

ILOs defined at three levels

Level 1: What concepts should a student know/remember/explain?

By the end of the course, the students should be able to ...

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

Level 2: What basic practical skills should a student be able to perform?

By the end of the course, the students should be able to ...

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

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

By the end of the course, the students should be able to ...

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

Grading

Course grading range

Grade Range Description of performance
A. Excellent 86-100 -
B. Good 71-85 -
C. Satisfactory 56-70 -
D. Poor 0-55 -

Course activities and grading breakdown

Activity Type Percentage of the overall course grade
Labs/seminar classes (weekly evaluations) 0
Interim performance assessment (class participation) 100/0
Exams 0/100

Recommendations for students on how to succeed in the course

Resources, literature and reference materials

Open access resources

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

Closed access resources

Software and tools used within the course

Teaching Methodology: Methods, techniques, & activities

Activities and Teaching Methods

Activities within each section
Learning Activities Section 1 Section 2
Midterm evaluation 1 1
Testing (written or computer based) 1 1

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

Activity Type Content Is Graded?
Question How a convex set and a convex function are defined? 1
Question What is the difference between polyhedron and polytope? 1
Question Why does always a linear program include constraints? 1
Question Consider the problem:




Solve it using simplex method.		 0
Question Consider the problem:




Solve it using cutting-plane and branch-and-bound methods.		 0

Section 2

Activity Type Content Is Graded?
Question Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem? 1
Question What is the goal of a descent algorithm? 1
Question What does it mean to fit some experimental data points 1
Question Consider the problem:

Solve it using the suitable method.		 0
Question Consider the problem:



Solve it using the suitable method.		 0

Final assessment

Section 1

  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

  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?

The retake exam

Section 1

  1. Consider the problem:

Solve it using simplex method.

  1. Consider the problem:

Solve it using cutting-plane and branch-and-bound methods.

Section 2

  1. Consider the problem:

Solve it using the suitable method.

Retrieved from "https://eduwiki.innopolis.university/index.php?title=MSc:_Optimization&oldid=7755"