It is the purpose of this study to contribute some scientific data toward the construction of a more valid rating scale for use in the classroom situation.

The following study was undertaken to discover some of the ways in which high school students who are popular differ from those who are not so popular.

Matching problems arise in several real-world scenarios like assigning posts to applicants, houses to trainees and room-mates to one another. In this thesis we consider the bipartite matching problem where one side of the bipartition specifies preferences over the other side. That is, we are given a bipartite graph G = (A ∪ P,E) where A denotes the set of applicants, P denotes the set of posts, and the preferences of applicants are specified by ranks on the edges. Several notions of optimality like pareto-optimality, rank-maximality, popularity have been studied in the literature; we focus on the notion of popularity. A matching M is more popular than another matching M′ if the number of applicants that prefer M to M′ exceeds the number of applicants that prefer M′ to M. A matching M is said to be popular if there exists no matching that is more popular than M. Popular matchings have the desirable property that no applicant majority can force a migration to another matching. However, popular matchings do not provide a complete answer since there exist simple instances that do not admit any popular matching. Abraham et al. (SICOMP 2007) characterized instances that admit a popular matching and also gave efficient algorithms to find one when it exists. We present several generalizations of the popular matchings problem in this thesis. Majority of our work deals with instances that do not admit any popular matching. We propose three different solution concepts for such instances. A reasonable solution when an instance does not admit a popular matching is to output a matching that is least unpopular amongst the set of unpopular matchings. McCutchen (LATIN 2008) introduced and studied measures of unpopularity, namely the unpopularity factor and unpopularity margin. He proved that computing either a least unpopularity factor matching or a least unpopularity margin matching is NP-hard. We build upon this work and design an O(km√n) time algorithm which produces matchings with bounded unpopularity provided a certain subgraph of G admits an A-complete matching (a matching that matches all the applicants). Here n and m denote the number of vertices and the number of edges in G respectively, and k, which is bounded by |A|, is the number of iterations taken by our algorithm to terminate. We also show that if a certain subgraph of G admits an A-complete matching, then we have computed a matching with the least unpopularity factor. Another feasible solution for instances without any popular matching is to output a mixed matching that is popular. A mixed matching is simply a probability distribution over the set of matchings. A mixed matching Q is popular if no mixed matching is more popular than Q. We seek to answer the existence and computation of popular mixed matchings in a given instance G. We begin with a linear programming formulation to compute a mixed matching with the least unpopularity margin. We show that although the linear program has exponentially many constraints, we have a polynomial time separation oracle and hence a least unpopularity margin mixed matching can be computed in polynomial time. By casting the popular mixed matchings problem as a two player zero-sum game, it is possible to prove that every instance of the popular matchings problem admits a popular mixed matching. Therefore, the matching returned by our linear program is indeed a popular mixed matching. Finally, we propose augmentation of the input graph for instances that do not admit any popular matching. Assume that we are dealing with a set of items B (say, DVDs/books) instead of posts and it is possible to make duplicates of these items. Our goal is to make duplicates of appropriate items such that the augmented graph admits a popular matching. However, since allowing arbitrarily many copies for items is not feasible in practice, we impose restrictions in two forms – (i) associating costs with items, and (ii) bounding the number of copies. In the first case, we assume that we pay a price of cost(b) for every extra copy of b that we make; the first copy is assumed to be given to us at free. The total cost of the augmented instance is the sum of costs of all the extra copies that we make. Our goal is to compute a minimum cost augmented instance which admits a popular matching. In the second case, along with the input graph G = (A ∪ B,E), we are given a vector hc1, c2, . . . , c|B|i denoting upper bounds on the number of copies of every item. We seek to answer whether there exists a vector hx1, x2, . . . , x|B|i such that having xi copies of item bi where 1 ≤ xi ≤ ci enables the augmented graph to admit a popular matching. We prove that several problems under both these models turn out to be NP-hard – in fact they remain NP-hard even under severe restrictions on the preference lists. Our final results deal with instances that admit popular matchings. When the input instance admits a popular matching, there may be several popular matchings – in fact there may be several maximum cardinality popular matchings. Hence one may not be content with returning any maximum cardinality popular matching and instead ask for an optimal popular matching. Assuming that the notion of optimality is specified as a part of the problem, we present an O(m + n21 ) time algorithm for computing an optimal popular matching in G. Here m denotes the number of edges in G and n1 denotes the number of applicants. We also consider the problem of computing a minimum cost popular matching where with every post p, a price cost(p) and a capacity cap(p) are associated. A post with capacity cap(p) can be matched with up to cap(p) many applicants. We present an O(mn1) time algorithm to compute a minimum cost popular matching in such instances. We believe that the work provides interesting insights into the popular matchings problem and its variants.

本研究欲跳脫教師教學評鑑的角度，探討大學教師不受學生歡迎的行為概況，並分析學生的知覺、反應與背後原因。研究採問卷調查法，以自編之「學生對於大學教師行為的知覺調查問卷」為研究工具，分二階段進行，以便利取樣方式選取公私立大學學生，有效樣本共1105人。問卷回收後進行資料的整理歸類，並以描述性統計、T考驗、單因子變異數分析等方法進行統計分析。本研究的主要發現如下： 1、歸納共得出七大類大學教師不受學生歡迎的行為：授課內容不適當、教學技巧缺乏、教學態度不佳、處理作業評量不適切、缺乏專業倫理、缺乏做研究的熱忱、其他。對於「最不喜歡的大學教師」，學生特別容易知覺到教師有第三類情況。而對於「一般的大學教師」，學生則特別容易知覺到第一與第二類情況。 2、在學生知覺教師出現不受歡迎行為的發生頻率上，公立大學生比私立大學生高；商管學院比其他所有學院高。 3、男大生在教學態度不佳上知覺到的發生頻率比女大生高；高年級的學生在教學態度不佳與缺乏專業倫理上的知覺比低年級的學生高。 4、在學生是否主動反應其知覺給教師知道上，不管學生喜不喜歡教師，當大學教師出現不受歡迎行為時，學生普遍「不會」主動反應其知覺使教師知道。比較其背景，則發現私立比公立大學生還不會反應；理工學院比其他學院學生 5、在學生不會主動反應的原因上，歸納共得出以下四大類學生不會主動反應其知覺的原因：溝通恐懼、不願意溝通、合理化教師行為、無主見。對於「最不喜歡的大學教師」時，不告知的原因較偏向第一項；對於「一般大學教師」，不告知的原因則較偏向第二與第三項。 本研究最後根據研究發現與結果，對教學實務方面與未來研究方面提出具體建議。 關鍵字：高等教育、師生關係、學生知覺、教師不受歡迎行為 / To probe into college teachers’ unpopular behaviors, students’ perception, and the causes of students’ reactions, this research conducted a two-phase survey of 1105 college students and its following analyses, instead of focusing on present teaching evaluation system. The first study was designed to elicit inductively student reports of the unpopular behaviors of college teachers. Responds to an open-ended questionnaire indicated 75 different items subdivided into seven categories of unpopular teacher behaviors, and 24 different items subdivided into four categories of reasons why student don’t respond their feelings. The second study was to quantify the unpopular teacher behaviors experienced by students, and compared student background as school, domain specific, gender, and grades. The main results were: 1. There are two dimensions of the most frequently selected teachers’ unpopular behaviors perceived by students: (1) Unprepared / Disorganized: result in boring lectures, failing to provide full explanations or practical examples, jumping from one subject to another, and giving confusing / inconsistent instructions. (2) Lack of communication: result in assuming students has a based knowledge for the course, and talking too fast or rushing through the materials. 2. Over 70% of students would not respond their feelings, and the most frequently selected reasons were communication apprehension and considering others would make the move. Other reasons included rationalization of teachers’ unpopular behaviors, and did not have ideas of one’s own. 3. After compared the frequencies of college students perceived their teachers’ unpopular behaviors, and the percentage of non-responding, and the statistics of reasons why student don’t respond, the results revealed that there were significant differences within students’ background. According the results of the survey, this research also provided several specific suggestions about future teaching behaviors and related researches. Keywords: Higher Education, Teacher-student Relationship, Student Perception, Unpopular Teacher Behavior